Currency exchanges do not seem to deal in foreign coins, at least here in New Zealand (I've exchanged US dollars and Japanese yen, personally). The exchange rate will also differ depending on exactly what exchange you use.
If you're trying to maximize the amount of NZD that you receive, definitely check the exchange rates offered by various currency exchanges, as other answers suggest.
If you're trying to end up with as close to 0 JPY as possible, then denominations and coinage matter. If you exchange your money in Japan, you will be able to spend Japanese coins, but most likely only in increments of NZ $5 (or larger, if the exchange does not stock small notes). If you exchange your money in New Zealand, you will be able to buy NZ coins, but you can only spend in increments of ¥1000. So, you would want to try to spend or convert your Japanese coins before departure, and then once in New Zealand you can convert any remaining Japanese bank notes into New Zealand bank notes and coins.
Note also that the ¥500 coin is currently worth more than the smallest NZ bank note (NZ $5) - if you end up with large coinage in Japan, it might be possible to exchange that for NZD, if you find an exchange which deals in small transactions and carries the NZ $5 note. If you wanted to do everything in a single transaction, exchanging on the Japanese side would then leave a smaller maximum remainder (somewhere between ¥350 and ¥400 might be left over if you exchange in Japan, whereas in New Zealand you could be stuck with as much as ¥999 - or more, if you didn't exchange coins for notes).
The one piece of info I don't have is whether Japanese currency exchanges deal with small New Zealand bank notes. I know that my bank sells ¥1000 notes, but I don't know whether Japanese exchanges would offer NZ $5 or $10 notes.