Does the Amazon App Store charge for updated apps?
No, Amazon does not charge again for apps you've already purchased.  You are misunderstanding the message that pops up.  When they say "Please find it in My Apps" they don't mean in your device's app drawer, they mean within the Appstore.  While you are still within the Amazon Appstore, do the following:


Open the side drawer (by sliding it out from left to right, tapping the Amazon logo on the upper-left corner, or simply pressing the menu button):

Select the "My Apps" option which is under the "Library" section:

Tap on the "Cloud" tab, and all of your previously purchased apps will be there, with an option to install on your new device:



You may need to refresh the list if it doesn't show up.