If this solution works for you, please add a message with details of your phone so others will know it might work for them.
Given the complete lack of response from Garmin regarding the VivoActive HR and it's constant failure to connect to Connect I guess it's still falling on the users to find a work around for their buggy software.
So here goes with a solution for the Zenfone 6, running Android 4.4.2 and the latest Garmin releases for the VAHR, 3.40 and Connect 3.13.1.
Be warned tho, there may be some extra steps in here because I've tried following the drivel Garmin put out as 'instructions' that have never, ever worked for me. None of the hundreds of variant instructions they've spewed about the place randomly! :-D
Problem:
VAHR disconnects when moving far from phone - expected behaviour.
VAHR will never again connect to Connect no matter what version of Garmin's instructions you follow. Massive bug that hasn't been addressed for the past year, so probably never will be.
Solution:
1. Unpair VAHR, reboot phone, turn VAHR off and back on.
2. Start Connect, go to menu -> Garmin devices. Your device should be there, but not connected.
3. Click on it and it will tell you the device is registered to your account, but not paired.
4. Press to connect, then on your VAHR go to Bluetooth and 'pair'. Almost instantly the device will pair and the screen will change to 'setting up device'. Click 'show more' and you will see that it never connects and always times out.
5. Go to bluetooth on your phone, search for devices, find the VAHR and pair it, enter the code
6. Return to Connect where it should still be trying to find the phone, click 'show more details' and you will see it connect, set up etc!
Good luck, hope it works for you!
So the summary is that Garmin Connect doesn't pair properly so cannot connect. But, you can't pair it with the phone first.
So you need to pair using connect -> when Connect starts trying to connect to VAHR, pair it with your phone.
Hope this helps some other people who have spent more time pairing their device than they do exercising!