Turning off that notification setting should make the repeated notifications go away but I don't think that will stop the app behavior. I could not find anything causing this on my S9+. I only have Spotify on my phone and my Surface and have never connecte Spotify between them so the "connecting" issue made no sense unless it was trying to connect to Spotify servers. It was driving me nuts and I was pretty close to just uninstalling it as I really don't use it much at all on my phone any more. The post talking about battery usage piqued my interest so I went and looked and it wasn't shown to be using much battery and I didn't see it using much data either but I have it banned from using background data BUT I did notice that in the WIFI data tab, it was set to use as much background WIFI data as it wanted and there was a fair amount. I went ahead and added it to the Always Sleeping Apps list. In fact, I added a whole gang of apps to the list. I'm absolutely sick to death of apps constantly starting and running in the background for unexplained reason, like a word game that I sometimes use (I haven't in 2 weeks) shouldn't be connecting 30 times a day. I realize a lot of apps only do this to see if there's an update but the Play Store does this for us so the only other reasons would be to check for somekind of notification about music we like or download files about how we use our phones and I'm sick of that too.
Still absolutely no clue what Spotify was trying to connect to or why, but if banning it from running unless I actually start it solves the issue, it'll get to stay on my phone for now. This is twice I almost uninstalled it because it was mysteriously starting. At least this time it wasn't opening up on it's own. That one actually did get me to uninstall it but I wiped the data and reinstalled it and it seemed to behave. I didn't even bother with that this time. I don't think it should be necessary as I have only had this phone for over a month and I installed the app from a fresh state. It was probably an update that caused the issue.
It seems that no moderators or Spotify team members have responded since people started posting on this thread 3 weeks ago so maybe a new thread should be started.