I just changed phones. How do I get Pro again? Do I need to pay for each new device I use it on?

You don't have to do that, of course. Just make sure you download EssentialPIM from the Google Play Store using the same account you previously purchased the Pro version of the app with. For additional info, please see here: https://support.google.com/googleplay/answer/113410?hl=en.