It is not really true at the moment that you can pay fees in anything except ETH, although there is some discussion about changing this. The way things normally work, you have to pay the fee in ETH. When you sent REP to the exchange you probably used ETH in your own account to deposit tokens in the exchange, and the exchange would have paid for the transaction to send them back out.
In theory, since it's up to the miner whether they include your transaction, you could send a low or zero fee in ETH and have a separate arrangement with a miner where you would give them some ERC 20 token, or send them USD via PayPal, or FedEx them a chicken. This depends on the miner thinking what you are giving them is valuable and being prepared to accept it as payment. If you've sent them a chicken but they don't want one, or you've sent them an ERC 20 token that they've never heard of and don't consider valuable, you shouldn't expect them to mine your transaction.