If you'd purchased on Google Play, you should be able to install the Unlocker from there, without paying again -- as long as you'd set up the new phone with same @gmail account as the old one, so Google recognizes you.
If you did, and Play still asks for a payment -- please try installing the Unlocker using a web browser, same link, just open it on your Windows PC if you use one:
https://play.google.com/store/apps/details?id=org.kman.AquaMail.UnlockerMarket( explanation: Google Play *app* on a *new* phone can be very slow to sync your purchases )
If Google Play web site *still* asks you to pay -- please contact me at kmansoft / gmail, there is a different way.