I recently upgraded to an S10+ and ran into this issue with my 2019 Ford Edge. I narrowed down the problem to recently using Bixby Routines. I deleted the Bluetooth auto connect routine and that didn't fix the problem. Since you cannot uninstall Bixby Routines I just deleted all the routines that I created and thent went into the setting to turn off Bixby. That fixed the problem and the Bixby Routine app is gone.
I have the 2018 model of the Galaxy S9 Plus. After a recent Android software update, my 2014 Nissan Rogue stopped connecting automatically via Bluetooth. The fix above worked and the Nissan/Samsung now connect automatically.