Bluetooth audio devices stop working after a few minutes
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.