I've got a S9 (and a Galaxy Tab that's doing the same thing), both of which work fine with BT devices I paired last year... Using BT the phone pairs to my car no problem and plays music through my speaker like always, no issue. But, it can't find any new devices. I purchased a second UE Boom 2 speaker... doesn't show up the in the list when scanning. My S7 finds it no problem. (My S7 can pair to both the Boom's no problem and output to both using the Boom app which the the point of the new purchase.) Try to pair it with my surround sound reciever... can't find it. My S7 finds it no problem.
I'm guessing some security feature or something has been enabled at some point that's blocking BT scanning from finding/reporting new devices. Rebooting, turning BT on and off, resetting network settings, allowing the device to discover new devices, etc. is not working. Since it works fine with the exact same device, I know BT itself is working, so any ideas on what can block discovery of new devices?
I would recommend trying to wipe the cache partition on your device. The system cache partition stores temporary system data. It's supposed to allow the system to access apps more quickly and efficiently, but sometimes things get cluttered and outdated, so a periodic cache clearing can help make the system run more smoothly. Give these steps a try:
Do you experience these symptoms if you try to pair the device while your phone is in safe mode? If your phone is misbehaving, it's possible that a third-party app is causing the issue. To figure out what app is acting funny, you can use the Safe Mode feature. In Safe Mode, your phone won't run any third-party apps. This allows you to easily identity and remove the app that may be causing the problem. Give this link a try: https://www.samsung.com/us/support/answer/ANS00062983/