If you change both phone and watch, then in my experience it’s smoothest to:
1. Unpair old watch from old phone.
2. Pair new watch to old phone with restore from watch backup
3. Transfer to new phone (wired quick start is fastest). That includes the watch transfer.