Here's what worked for me.
Back story: unlocking with my watch was working fine until one day it randomly stopped. I turned off Handoff on my Mac and iPhone, and then back on again, but that didn't make a difference. However, I did notice that the Handoff feature didn't seem to be working anymore (e.g. look at a safari page on iPhone, then on Mac press command + tab -- Safari should appear on the far left with a phone symbol to show you can use Handoff). So even though I had Handoff "on" for my devices, it didn't seem to be working.
Solution (some steps may be redundant):
1. I turned off Handoff on my Mac and iPhone, and for good measure I signed out of FaceTime on iPhone and Messages on Mac (because I read in a another thread it may help).
2. I restarted the Mac and iPhone
3. I switched all the options back on, including Handoff
4. I verified Handoff was definitely working
5. Turned on the "Allow your Apple Watch to unlock your Mac" -- no error message this time
6. Verified Apple Watch unlocks Mac - yay
7. Profit with all that time saved not having to write passwords anymore 🙂
Good luck.