I got it working by setting the 2FA in the Mac preferences then signing out and back in again on all my devices. You should also check the iCloud security screen on your iPhone to make sure it recognizes that 2FA is enabled. Once those are all in sync, reboot everything.
My issue is that having it actually unlock your Mac is a hit and miss. So far I have tried to show it off to 3 people here at office and on ALL 3 occasions it didn't work. However, when I tried it just before, it worked fine.
Of course when it doesn't work there is no way to tell why. I wish there was a way to determine why it didn't work so we can help solve the issues.
In order for this to be useful it MUST be more reliable.
I have noticed that in order for it to work your phone needs to be close by and UNLOCKED.
I had phone phone in my pocket locked with a passcode (like it usually is) and the auto unlock did not work. I tried several times. However, once I took my phone out of my pocket and unlocked it the auto unlock for the Mac started to work. Is this feature "unlock your mac with your Apple Watch" or "Unlock your Mac with your iPhone"?