Auto Unlock not working on MBP Early 2013 - iOS 10 - watchOS 3.0 - macOS Sierra GM For some reason, I cannot get "Auto Unlock" to work. 

Currently running macOS Sierra GM on a MBP Retina Early 2013, watchOS 3.0 and iOS 10 GM.

I've already disabled Two-Step verification and enabled Two-Factor verification for my Apple ID. All devices appear registered on iCloud devices.

Any ideas of what could be the reason?
As mentioned in other answers, the auto unlock feature is officially supported only on Macs that were introduced after mid 2013, and include both Bluetooth 4.0 and 802.11ac. As an owner of a 2012 retina MacBookPro, I was disappointed to find that the feature did't work. 

However, it is pretty easy to replace the older Airport chip with a newer one that is used on mid 2013 models (model number of the chip: BCM94360CSAX, can be found on eBay etc for around $10 or so). After replacing the chip, the option for auto unlock appears on the preferences and you should be good to go (for me, required also nvram reset and logout from iCloud). Obviously the operation voids warranty, and some have reported it to cause issues on OS X recovery install over wifi. Still, it seems to be currently the only option for enabling the feature, and as an added bonus you get also the better transfer speeds of an 802.11ac chip.