This started happening to me too after an OS update. Tried the advanced settings in Pandora for turning of bluetooth auto launch, tried the prevent USB auto routing in developer options. Then realized it was an issue with android auto (at least on my phone). I did not have to be connected to the car. Whenever I opened android auto, even standalone, Pandora would start up.
So, I went to settings > apps > android auto > storage and cleared cache and data. Then, I opened android auto holding the phone in my hand (not connected to anything) and went to settings > Autolaunch and deselected all of the bluetooth devices and made sure autolaunch was deselected.
Went out to the car, plugged it in, let it go through the initial setup, and all has been good since. Hope this helps someone. May not work for all, but is worth a try.