No entries in Amazon App Store on new (refurbished) Fire phone
The problem is caused by the Kindle account belonging to Amazon US (amazon.com) and the Amazon account belonging to Amazon Germany (amazon.de).

With a new Amazon account, all works fine.