Ok update with more details:
I have two Macs, and both were having this problem with my new (used) Apple Watch 5. Neither had issues with Auto Unlock on my Apple Watch 3. I followed these workaround instructions for my MacBook Pro, and after a few attempts it worked. Can't really say why it took several attempts.
Then I tried my Mac Pro, same procedure about ten times. I avoided deleting the iCloud Auto Unlock keychain entry for my MacBook Pro, since I just created it and didn't want to get into a loop of fixing one while breaking the other. I finally decided to simply turn off the iCloud Keychain in System Preferences > iCloud and delete all the Keychain entries and Sharing preferences, then reboot and turn on the iCloud Keychain again. Then I remembered another thing I tried on the MacBook, making sure the Mac and iPhone were on the same wifi network (I have a 2.5 and a 5ghz on my Airport). Also, I made sure Unlox wasn't running (I use Unlox to enter the system password and as a backup in case Apple Watch unlock fails, and they've always gotten along fine together, but I thought it might be interfering at setup). After this, the Mac Pro setup took... but then the MacBook Pro stopped working!!!
Fortunately, this time the MacBook Pro took only one attempt to get it working again. Now all is good again with both Macs.