So the Galaxy Watch 6 uses the Galaxy Wear app, which uses another application called Galaxy Watch6 Plugin. I suspected the latter was at fault as it was updated on March 5th. I downgraded the plugin app to a the November 2023 version and tried to factory reset the watch.
I ended up with the exact same problem. Initial pairing works fine, but if I go in airplane mode, it doesn't connect back nor will any devices connect to the phone until I turn off Bluetooth on the watch.
Disabling exploit protection has no effect either.
It used to work fine before the qpr2 grapheneos update. Did not test/flash back pixel os to test.