I have Spotify on Windows 10 and on my Samsung phone, and I have a Premium account. I have Sonos and a bunch of Google Chromecast/Home devices.
When I try to cast from Spotify on my desktop it invariably shows no devices, even though I can cast to all the Sonos and Google devices from anywhere else in Windows.
However if I open my Android app, it always lists the devices, and as soon as I cast to one of them, a whole lot of devices now show up in the Windows desktop app.
The weak link appears to be the Spotify desktop app.