There are several ways that programs can automatically start in macOS:
First check "Login Items" which are found in System Preferences after clicking the "Users & Groups" icons. I understand that you have already checked here and did not find Spotify.
Another possibility is that Spotify have been set to open at login from the dock. You can right-click the Spotify icon in the dock, and then in the Options menu make sure that "Open at login" is not enabled.
Similarly if you have left Spotify running when you power down the Mac then by default the app and open windows will be opened again after rebooting. You can avoid this by ensuring that you close Spotify before logging out or rebooting, or change the setting in general by clicking the "General" icon System Preferences and making sure there's a checkmark in "Close windows when quitting an app".
A third possibility is that it is possible to create configuration files for
launchd that will automatically start programs at boot or login. You'll find these configurations files in:
Note that the ~ characters means your user's home folder.
A final possiblity is that applications in macOS can come with a "shared helper application". Essentially this application would provide some background service to one or more actual applications from that developer. Some use that helper application to later launch their actual application.
The helper application is located within the application's bundle in the
Contents/Library/LoginItems folder. For Spotify that is usually in the following location:
You can prevent that from autostarting Spotify by closing the helper app, or making sure that it cannot start (for example by removing the executable bit on the actual executable: