I found the fix for my issue and it wasn't with the phone necessarily. My Subaru has 2 ways to connect bluetooth devices... the easy way (menu option on stereo) allowed me to pair but for some reason it wasn't auto connecting. S7 had no issues when setting it up this way. I decided to try the long setup option (thru the voice prompt on steering wheel), so I deleted the phone from my car's bluetooth and started the process over. This time when I restarted my car it automatically connected my phone. Simple fix but annoyed that there is nothing on this from samsung and I never had this problem with the s7 so seems like a software change on the phone.
Same problem. Deleted phone from my car audio (Subaru Forester 2015). Reconnected. Unpaired my phone, re-paired, toggled off nearby device scanning, restarted phone, toggled back on nearby device scanning, still not autoconnecting.
Try deleting the phone from car audio first, then use the talk button on the steering wheel and say "phone setup". Follow pairing the phone this way, through "push to talk" button. This is what fixed it with my 2014 Forester.