Bluetooth issues with Handoff

I cannot get Handoff set up properly. For the longest time I have had issues with pairing my phone to my Mac. That was when I had an iPhone 5S and Macbook Pro. Now I have an iPhone 7 and Macbook Air and have everything enabled and connected properly - except Bluetooth. I cannot pair my phone to my Mac via Bluetooth. It says "Connected" for approximately one second before it says "Not connected" again. I try to pair from my phone and I get "Connection Unsuccessful - Make sure '[my laptop name]' is turned on and in range."

Any ideas?

 

Update: It still says "Not connected" on my Mac, but Handoff has started working.