Your Mac was unable to communicate with your Apple Watch.

Something mysterious about this whole thing.

For two days I have followed all the proposed methods, especially the one to erase the auto unlocks from the keychain, on my macbook from 2017 and on my mac mini from 2018, without success, a thousand times.
Today I updated my 27-inch imac from 2012 and the unlock option with the apple watch was successful on the first try. Then it occurred to me to try it on my mac mini and surprisingly I also got it on the first try this time. And then  i tried on my macbook and GOT IT AGAIN on the very first time,  not so surprisingly now.
 I think that part of the proposed solution to erase auto unlocks and so,  is trying to activate the unlock on all computers within the same icloud, once updated. Maybe, the system need to check ALL computers included in the icloud everytime auto unlock is required. What do you think about?

I tried this and it worked for the first "sleep/wake" with the watch. But the 2nd time it did not. So I followed the above steps again. I noticed there was a 5th AutoUnlock (step 7) with a "piggy" suffix. Deleted this , too. Also, in System, Privacy "Disable automatic login" was checked (what does this do?). I unchecked it and checked "Use your Apple Watch...". Put Mac to sleep, pressed space bar, Mac opened using watch. Fingers crossed for the future.

For anyone like me that was desperate and went through this entire thread and followed everyone's suggestions without any luck, do everything listed in realstuarthobbs post. Then WAIT. I spent a few hours following everyone's suggestions to no avail. Finally, I decided to give up. I came back to my computer the next day and everything suddenly worked.

So, Im not sure which of the things I did, but I got it to work. I followed the reply marked as the answer and that didn't work. I then tried the solution offered by duZ3N and that also did not work. I realized that I hadn't rebooted my computer. After I did that, I tried 2 times and it worked the second time. One of them worked, but Im honestly not sure if it was one or both but for sure the reboot was the key to either one. Hope this helps and thanks you other guys for providing a solution.

I have tried this - more than once - with and without reboot but no resolve.

Also I see this in the syslog:

Nov 13 11:21:00 jonass-5k-imac com.apple.preference.security.remoteservice[20503]: objc[20503]: Class AWDSecurityPrefAutoUnlockSetup is implemented in both /System/Library/PreferencePanes/Security.prefPane/Contents/XPCServices/com.apple.preference.security.remoteservice.xpc/Contents/MacOS/com.apple.preference.security.remoteservice (0x1037b0768) and /System/Library/PreferencePanes/Security.prefPane/Contents/MacOS/Security (0x106343770). One of the two will be used. Which one is undefined.

To me this seems like an issue with migrated configurations (was using latest Catalina before this).

Hope for a patch soon.

I tried these steps a number of times, doing more log out of icloud and restart each time. I'm not entirely sure which version finally got it to work (possibly I hadn't restarted the mac after deleting the two plist files) but eventually I did get the checkbox to re-enable.

At this point iCloud services are just a hopeless mess of random issues like this. Handoff works occasionally but mostly not, iCloud tabs between devices failed weeks ago (there's several huge threads about this) and it took me all morning and lots of random keychain editing to sort this one out. Thanks to all those who posted, trying everything except from an unpair-repair of the watch eventually got at least this one service re-enabled.

When you go through Step #4, make sure you delete all the "auto unlock: xxxxx's" I had one for the computer and phone, but didn't delete those first time around. When i removed them it all worked!

this solution seems to be working for me from my Watch Series 5 to my MacbookAir 2019. I did have to do a restart on the MacOS before the lock preference was enabled. Very convoluted work around, but well it worked. Thanks for nothing Apple.. Now onto the other zillion problems I am having with Watch OS 7 ....

The solution by mark__t worked for me. Just one observation. When you get to step 9 you might have a little problem with locating the Sharing/AutoUnlock folder inside ~/Library as it seems to be a protected folder. I like to use the terminal to get to stuff instead of the finder and saw messages like "operation not permitted" for listing (ls) or deleting those files as suggested in step 10. I had to go into the "Security and Privacy" widget in "System Preferences" and make sure that "Terminal" was added as an app for "Full Disk Access" under "Privacy". Simply using "sudo" on the command line does not grant elevated access. Other than that it did finally solve my mystery with not being able to use my Apple Watch to unlock my Mac.

I have tried all the "Solved" process and rebooted all devices and Mac still doesn't see the Watch 4. All are running Latest Dev Betas. It worked before the Big Sur beta update 11.0.1 Beta (20B5012d) even with latest iOS beta updates so that tells me it's the MAC OS update not the iOS and Watch updates.

I unpaired my watch then re-paired and after second selection of the unlock option it worked. I may not have waited long enough for all to complete bootup so maybe if I waited 5 or 10 more min after re-pairing and letting all apps restore it may have worked first time.

This worked for me. I found using finder to get to sharing was annoying so I just used terminal. Be sure that terminal is granted full disk access or you won't be able to enter the Sharing/Autolock directory to delete the files.

Very frustrating - with the upgrade to Big Sur on both my iMac Pro and MacBook Pro, I had this issue suddenly occur. I followed the above steps and because of the iCloud sharing, deleting files on the iMac Pro wiped out those for the MacBook Pro too - not unexpected. But the MacBook Pro simply let me check the box for unlock via the Apple Watch and now it is happy. The iMac Pro, not happy at all. I also toggled the KeyChain as suggested below but that did nothing. Cleared PRAM as as well, and still nothing. Having seen the note from TigerGTO, I have stopped short of a full scape and pave to reinstall iOS.

Clearly there is a bug rather deep in something that is affecting some systems but not others. My iMac Pro and MacBook Pro are essentially twins so far as core software goes. Very odd

After updating to Big Sur on my iMac the communication was no longer possible. It still works with my work MBP that I also updated to Big Sur. Kinda confused here. I also tried on/off the Handoff on the Watch, same result. I think we have to wait for a patch for everyone to be happily unlocking our macs with our watch.