I had the same problem, (new mac book air m1) I tried the turning handoff on and off and restarting solution, but it did not work for me. I fixed it by turning on iphone hotspot via the macbook wifi menu. once it connected for the first time the handoff got fixed