Your license of the game is linked to the Google Account you used to purchase the game, and you will never lose it as long as you keep your account. If you have that Google account added to your device (under Settings/Accounts), the license should be autodetected. You can force another license check using the "Restore Purchase" button in the Store menu.
However, in a few cases the license might not be detected even if you use the "Restore Purchase" button. In almost 100% of the cases it is because of multiple accounts added to your device, confusing the license manager. Please remove all the other accounts on your device temporarily, until the license is properly detected (they can be added again). If you are unsure on which of your accounts holds the license, you can check it at Google Payments site.
If after trying this you are still not able to recover your license, contact us.
Your license and your saved games are different things. If you want to transfer your saves from one device to another you will need to use the options under Main Menu > New Game > Export& Cloud. Exiled Kingdoms is an off-line game and there are no servers keeping your data, it is all in your device. If you uninstall without exporting your data first, you will lose your saves.