In the console.app I could find nice informative lines like:
IOBluetoothUSBDFUTool: Could not get IOBluetoothUSBDFU service
I went through tonnes of blogposts and forum posts with all kinds of advice. Mostly coming down to:
- Unplug all USB devices, shut down and the restart
- Reset your SMC
None of this really worked. I then started the Mac in Safe mode by keeping the shift key pressed. Now I was able to use Bluetooth. Of course, you can't boot your Mac in Safe mode all the time..... But still this indicates that some 3rd party component was messing up. Possibly a kernel extension, or at least a preference connected to a kernel extension.
I have a few elements installed, but I went with my gut feeling.. Logitech. I own a very nice M500 corded mouse, but the Logitech software has given problems with MacOS upgrades etc before and Googling around indicates I'm not the only one with this experience. I downloaded the installer and reinstalled Logitech (even though I already had the latest version installed). And low and behold. One reboot later things work again...
Not sure if it indeed was Logitech, or that Logitech just triggered a process that kicked the Kernel extension loader in some way to fix my issue, but at least I can use Bluetooth again.