I solved this problem by completely logging out of iCloud on my MacBook (Monterey 12.1) and then on my phone. It's a bit of hassle but it worked, when I signed in again I had re-set up some of iCloud stuff like Apple Pay etc. but it doesn't take too long if you have decent internet.
When I was busy setting it up it picked up that I was using a different language on the phone and the MacBook (two different regional variations of English) and I think it may be a requirement for handoff - maybe check your language options on the two devices first to see if they are the same.
I did not work immediately when I tested it but after a few minutes it worked. I think possibly it has to some cloud security stuff before it works properly.