Hello darshi5,
Have you already had a chance to complete the steps for that type of issue from this page: How to pair your Apple Watch with a new iPhone - Apple Support
If the steps on that link were already completed, there are a few other things to try out.
Try restarting both the iPhone and the Apple Watch to give them a quick refresh:
Restart your Apple Watch - Apple Support
Restart your iPhone - Apple Support
Ensure the iPhone is on the latest version of iOS as well, which is currently iOS 16.1, as this will help apply the latest improvements/fixes: Update your iPhone or iPad - Apple Support
It may also help to try uninstalling the Watch app from the iPhone, and then re-downloading it from the App Store.
If you have any VPNs installed on the iPhone, try temporarily uninstalling them to rule out any possible conflicts.
Cheers.