If you're running Windows 10 and can't get Spotify to stop opening when Windows starts - even with the startup option set to "No" in the Advanced section of Spotify's preferences - you may have the Windows app store version of the program installed, even if you don't think you have. So try this:
This worked for me. Your experience may differ. I had even used CCleaner and other methods to change startup entries without success until I tried the above procedure.
I believe this is a problem caused by Windows being confused because it is possible to have downloaded and installed Spotify from the Spotify website as a regular program, and it is also possible to have downloaded and installed Spotify from the Windows app store as an "app".
If you've d'loaded it as a Windows app, you need to configure the Windows settings as described above (in addition to the regular "Edit > Preferences > [Show Advanced Settings] > Startup and Window Behavior >Open Spotify automatically after you log into the computer > No" fix within Spotify).