This is EXACTLY what is happening with my Gear S3. It drives me totally bonkers when I’m out running to the point I want to smash the thing to pieces! Was totally the reason I bought the thing. It’s so temperamental! Utter tripe.
Turn on wifi on watch and spotify, start playing downloaded mudic and turn off wifi on watch. It should play dowloaded songs offline. Also keep in mind the manual states that after 1 GB is full of downloaded songs, it starts to overwritten the oldest ones. Total memory on S4 is 4 GB.
This question is marked as solved, and this particular message is identified as the solution. As the author of the message says themselves, it is NOT a solution. I don't know if Spotify tagged it as solved, but it is pathetic.
I was able to solve a problem with a playlist pressing the button download off after already downloaded all songs, then I press the button to download again. Apparently some verification is done and things start to work again.