I managed the solve this issue by
Unpair watch and iPhone from Xcode (right-click).
Quit Xcode and disconnect the iPhone (Airplane mode)
Remove trusted computers on both devices.
Disable developer mode
Restart both devices.
Connect the iPhone and trust the computer using Finder
Open Xcode and pair the iPhone (trust again)
Enable developer mode on watch and iPhone
It should work.
This was basically following the advice in this post + unpairing the devices from Xcode:
https://forums.developer.apple.com/forums/thread/734694?page=2