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.