All of those things are true. The two Macs are within inches of each other, Handoff is on (and functional), Bluetooth and Wifi are on, same Apple ID, 2FA turned on. I'm a bit stumped here, honestly.
The only possible fly in the ointment I can think of is that on each of the Macs I run separate personal and work user accounts, signed in to different Apple IDs. Though when I've tried to get Universal Control working, I'm making sure they're both logged into my work account. I guess there could be some bug with the multiple users?
I'll try 12.4 when it comes out of beta, see if that helps, I guess.