This is not a spotify issue, it's a Windows 10 bug that was supposed to act like a "feature":
When you shut down your PC, all apps are closed
After reboot/restart, you have to re-open any app you'd like to use
If you want to start with no apps open (other than those set to auto-start via Task Manager/Start), you'll need to ensure all apps are closed before shutting down or restarting the PC.
I don't know about you, but I'm too lazy and am not going to close all my apps, one aften another, before I shutdown my PC. This is 2019, things should just work.
There are multple ways of solving this, but the most robust one is to create a shortcut in your startup menu to manually shutdown/restart your PC while forgoing on this annoying "feature". Here's a guide on how to do this, follow the method in Option 2(a) and then you can place your shortcuts in your startup folder (e.g. %AppData%\Microsoft\Windows\Start Menu\Programs).