An S10 is a relatively recent handset running a recent version of Android so will not be an issue.
The Watch not finding the handset to start with may well be that the handset's BT is not visible That said, the pairing to watch within Galaxy Wearable is initiated from the handset to the watch, and you've got them paired up successfully by the sounds of it if you are getting calls, notifications etc.
Spotify - have you paired the app on your Watch to the app on your phone? When the app 1st runs on the Watch it should ask you to pair then when you open Spotify on your phone it asks to confirm. That's all I did and I can access everything via the Watch, play on watch or control it playing via my phone.
Backups - the auto backup needs to be enabled and will not kick in unless connected to WiFi, battery levels above certain value, 24hrs since last backup, linked to an account. To get it started then you can force an initial backup, and if you are looking to reset your watch then just initiate and complete a manual backup before doing the reset.
When I got my original GW then I had a BT issue. Found that restarting both the handset and watch simultaneously fixed it & never had the issue again.