Sounds like a thermal sensor is bad on your phone. I know you tried a different battery, but have you tried a different cable/charger? Any battery monitoring apps installed on your phone? If so uninstall them to see if it makes a difference. You could download
Aida64 to check the battery temp... not that it'll do anything to help you fix this problem, but at least you can see what it is in case you need to contact Samsung or your carrier for support.
What happens if you start your phone in
Safe Mode. Does the popup still show up when you try to charge your phone?
As a last resort you may need to do a factory reset (if this is a software problem rather than hardware). But before you do, you will need to back up all data because a factory reset will surely wipe the phone.
EDIT>>> By the way, I just noticed that the context of your post doesn't match what the title states. Does your phone not even turn on?