and I assume you rebooted all 3 devices, watch, phone, Mac?
I had to do the procedure in post 3 on my iMac, once during upgrades to watchOS 7, running Mojave.
I'm running Big Sur public beta on my MacBook and have upgraded at least 4 times in the past 6 well have to eks, one time I had to toggle the "allow Apple Watch ..." on/off to get it working again.
so when you say you restored from backup, so you did a unpair with old phone and then restored - so for the Mac the watch looks like a new device, which means you will have to toggle that switch in system preferences ...
beyond that, not sure that I have any other idea at this point