The feature appears to require not only Bluetooth 4 but 802.11ac. Ostensibly this is because 802.11ac time of flight calculations are used to estimate the distance to the watch. (EDIT: It's not actually 802.11ac but 802.11v, but you need the newer network card to support 802.11v, see below.)
I feel for you, as I too cannot get my "Macbook Pro (Retina, 15-Inch, Early 2013)" to enable Auto Unlock. It's kind of frustrating that they state you need a model newer than 2013, when it's really a model newer than "early 2013."
EDIT: I agree that requiring AC doesn't seem to make much sense, since the watch itself isn't 802.11ac, but it seems to be true. Newer official content by Apple now state "mid-2013" instead of "early-2013" as the cutoff.
This blog post describes the process by which upgrading the network card to an 802.11ac card (BCM94360CSAX) enables the feature. Unfortunately, the complete instructions to upgrade your MBP by Mark Bingley are at a currently-broken link on another blog, though maybe this link will come back in the future.
Others have reported success after upgrading the wireless in an early 2013 MBP, and even a 2010 Mac Pro (apparently after installing a new wifi/BT4 card).
EDIT 2: Oh, and here's this for a "link to a reputable site" site that explains it. Apparently you need a modern network adapter to get 802.11v support (yes, v), which is used to measure network latency; in this case it is used to measure the lightspeed roundtrip time-of-flight to the Apple Watch to ensure you are within 3 meters for auto unlock.
Neither the Apple Watch nor the MBP use 802.11ac at all to communicate. The issue is that older network cards in Mac hardware prior to the mid-2013 MBPs (specifically BCM43xx adapters) do not support the 802.11v timestamp field. Or so that article states.
Allow Handoff
enabled, too. – fsb Sep 21 '16 at 21:02