Paypal fees are quite ludicrous, 2.75% if I remember right. I change from ZAR to USD quite often and use a company called exchange for free. They might not charge fees, but there is still a spread of around 1%. I go with them because my banks charge 2%.
I can exchange currencies at 0.1% and under through my interactive brokers account, but I have no way to withdraw or deposit in ZAR. This would work great for USD, EUR and GBP though as interactive have accounts in those countries. If they have one in Japan then you're all set, otherwise see if you can find another broker with accounts in both currencies.