I tried a whole bunch of additional things that are related to sound rather than bluetooth. The issue is now resolved. I don't know which of the steps fixed it but if you have the same issue, doing all of them will likely resolve it:
1. Reload coreaudiod
Enter the following into Terminal:
sudo killall coreaudiod
sudo launchctl unload /System/Library/LaunchDaemons/com.apple.audio.coreaudiod.plist
sudo launchctl load /System/Library/LaunchDaemons/com.apple.audio.coreaudiod.plist
Then restart the laptop (or do step 3 (below) at the same time).
I got errors when doing the above, but perhaps it still helped somehow.
2. Unload the kernel extension
sudo kextunload /System/Library/Extensions/AppleHDA.kext
sudo kextload /System/Library/Extensions/AppleHDA.kext
Again, I got errors when doing the above, but perhaps it still helped somehow.
3. Reset the SMC
Shut down the laptop, connect it to power, hold the four buttons cmd-option-shift-power for at least 10 seconds, release, start the laptop again.
--
After performing these steps, everything was back to normal.
I recommend you to reset NVRAM of your device.
This chip stores information on screen resolution and can often become corrupted. You can reset it by starting your Mac while holding down cmd + opt + P + R . You should hear the Mac chime, restart and chime a second time. Then you can release the keys you are holding. More info here.
Best Answer
Thanks fsb the SMC reset did the trick.