I have two fire sticks in my home and until recently Spotify worked perfectly on both of them all of a sudden one of the fire sticks won’t connect to Spotify but every other application on it works so I know Spotify is the issue
You can play Spotify on Fire TV Stick using either the native login option or Spotify Connect. You can use Spotify Connect and that will log you in anyway.
I personally use Fire TV Stick as well so I can help you out here. Just go into your App list, clean the App data and uninstall the Spotify App. Go ahead to install it again from the Store. This time when you open Spotify, make sure you are on the same WiFi network if possible and avoid using any VPN or DNS service.
Play something on your Mobile App and then use the Spotify Connect option to sync with the Fire TV Stick App. That should do it. You can also check out the troubleshooting steps here.