Apple Watch not unlocking MacBook Pro

From the Apple Support article How to unlock your Mac with your Apple Watch:

If you're having difficulty getting Auto Unlock to work, try these solutions:

• In Security & Privacy preferences, deselect ”Use your Apple Watch to unlock apps and your Mac” or ”Allow your Apple Watch to unlock your Mac.” Then restart your Mac and turn this setting back on.

• Make sure that your Mac isn't using Internet sharing or screen sharing.

It looks like you've tried the first step, but you may want to check your Sharing preferences.

If that doesn't resolve the issue, consider reporting a bug with Feedback Assistant.

Also, hate to state the obvious, but try a hard restart of your Apple Watch by pressing in the Digital Crown and the side button at the same time until the Apple Watch reboots and the Apple logo appears on the screen.

You may need to do this twice in a row.

Solves occasional connectivity issue that my Watch Series 3 has.

Every time you change your macOS password, you will most certainly face this issue. The solution as per my discussion with Apple support, is to reset the keychain.

I know it is a hassle but this is the only thing that works.

A couple of other things to try that worked for me in the past:

On the Mac in System Preferences->Apple ID->iCloud uncheck Keychain syncing then check it again.

Or

On the overview tab click sign out and sign back in again.