I hit this problem too, and managed to sort it out after a fairly significant amount of screwing around and reaching dead ends.
I'm assuming what went screwy for me was that I had to enable 2FA before enabling the option, which went smoothly and authenticated my Macbook, but there's no prompt to authenticate the phone, it wasn't until I went into Settings > iCloud on my phone and waited 10 seconds or so that I was prompted to authenticate it with a code (which was then sent to my Macbook) Once I authenticated the phone I went into the settings in my watch app to check everything looked fine, and then restarted my watch (probably not necessary, but I did it anyway) and once it started back up, unlocking via the watch started working.
If you've turned on/toggled 2FA and haven't authenticated both your phone and your computer, go into the iCloud settings on each and enter the codes from the other when prompted. My guess is this problem is happening for at least some of you because you've recently turned on 2FA to use it, but haven't yet been through the 2FA song and dance on your phone, since only your Mac will have prompted you do it at the time.
Some of you seem to have taken desperate measures though, I guess you guys are out of luck until the 20th :/
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.