Next time you can save yourself a reset by using adb.
- connect to watch over adb (usb or wireless)
- run
adb shell "pm clear com.google.android.gms && reboot"
- wait a few minutes (might not be necessary, but I found it increases success rate)
- run
adb shell "am start -a android.bluetooth.adapter.action.REQUEST_DISCOVERABLE"
- pair new device in companion app (I reset the app for good measure, don't know if it's needed)
Also on my device (oppo watch), play integrity doesn't seem to matter. Some of the time I'm only passing basic and watch works perfectly.
Very impressive, even if broken on high refresh rate devices.