How do I unpair my watch from a broken phone that had been signed in under a different iCloud?

Pair a watch with a new phone.

Start at the section "If you don't have you're old phone".

If you can't remember your old apple id then;

You can request an Online Activation Lock Removal here.

Or this;

If you can't remember/gain access to the apple id that paired the watch to the phone.Take the

watch and it's receipt along with some photo id and any other proof of ownership to an Apple Store

and request that they remove the Activation Lock for you.