zache Enabling notifications for Android Auto didn't fix it, but after I gave Android Auto call permission (handling calls) and turning on notifications for the Spotify app (in general), it's working now!
So either one, two, or a combination of all three of those, worked for me. :)