I suspect that the app will not appear for any non-Kindle devices at this time.
On my wife's phone (Nexus 5) I went to the Amazon Underground app and attempted to install Terraria. She has never installed it, but we share the same amazon account, so it shows up as purchased in her Cloud tab. For one thing, it shows the older version of the app in the list, and secondly, when I click "Install" I just get a message that says "Download Failed"
My assumption is that for non-Kindle devices, the version hasn't been updated, which makes the update not appear for us, as well as tricking our devices into thinking we have the latest version.