Manual hotspot connections work most of the time for me, but I have never been able to get "Instant Personal Hotspot" to work reliably.
All the Continuity stuff (Handoff, Personal Hotspot, Watch Mac Unlock, Universal Clipboard, …) started working far more reliably for me a few years ago when I did a (rather annoying) "purge" of sorts by taking each device one by one and logging it out of iCloud then back in.
That shouldn't be necessary and Apple needs to get their stuff together, but… y'know.