Thanks Kirk, your topic was the only one I found on the web and I've managed to fix it as well.
I did it by installing "Google Home" on my phone - in this application you can reset your Google Assistant connection with Free Spotify and reconnect with premium account.
Here is the procedure https://support.spotify.com/us/article/google-asssistant/ - I've copied it below, in case this link expires.
Since I've already had Spotify visible in that app I had to:
1. Select (temporary) Youtube Music as main music player
2. Click on spotify to disconnect it with google assistant
3. Click spotify again to reconnect it - now it should detect I have premium account
4. Select spotify as main musi player
5. Enjoy my life :)
I hope this helps even more people