After reading various replies to your post, I followed several options, but the one thing that worked for me was to check my iCloud settings on my phone (using a restored image of Beta after upgrade from iphone 6 to 7 plus.) My watch had previously worked just fine to unlock my MacBook Air... same o/s was simply restored on the new phone.
Issue was under Settings-iCloud-Keychain, Find My iPhone and iCloud Backup, were all set to "Off." Tried to enable only Keychain on, but would not hold setting. Would turn on, but then off when backed out. Once Enabled all 3 settings, then they held in "On" position.
Went back to MacBook Air settings, Security, checked the "Allow Apple Watch to Unlock Mac," and BOOM! It popped right on, without issue. Then tested unlock and working flawlessly, as before.
Long story short, your issue may have to do with iCloud security settings, which makes sense, since this is a shared pool of security settings.
I have the same issue. Did all the recommended things of rebooting everything , turning off sharing and so on. Still get the spinning wheel. Apparently its waiting to the watch to display allow $%^s MacBook Pro to access and push the side button on the watch twice to accept but that stage never happens. It seems the laptop doesn't see the watch. and is waiting for a response that is not going to happen. Im on a MacBook Pro 2021 14". My other Macs are working with the watch just fine.