Could not locate Spotify on AMZ market, and my attempts to sideload failed, but I was able to load after digging a bit for a kosher apk:
http://m.spotify.com/us/
and select 'download manually'. Bingo!
Sent from my Kindle Fire using Tapatalk