Doing this got rid of my "connecting to spotify" notification. If you've still got this issue, I suggest trying to turn off external applications. Settings > apps > spotify > notifications then switch off external applications.
Not sure if you have solved this issue. On my case I've been trying to make Spotify work with Waze and Google Maps. On these driving apps you can control music directly without need to jump between.
But for some reason Waze is not working.
At same time when expanding Spotify Connections notification, there's text "Waze is connected".
So you may find setting about this on Spotify. Disable or enable it.
On my phone Waze connection does not work since almost a year ago. But Google Maps does it well.
I hope this gives you some ideas to try.