Hello I'm having trouble trying to connect my Apple Watch to my new iPhone

From a web browser,sign in to iCloud.com with your Apple ID.

Go to Find iPhone.

Click All Devices at the top of the screen.

Click your Apple Watch.

Click Erase [device]. Select Next until the device is erased.

Click Remove from Account.

Then see this page;

How to pair your Apple Watch with a new iPhone

Make sure you unpaired your watch from your old phone to do this, open the Apple Watch app on your old iPhone go to > My Watch tab > All Watches > Tap the info button next to the watch that you want to unpair > Tap Unpair Apple Watch. ( Keep your Apple Watch and iPhone close together as you unpair them ). If you don't have your old phone anymore, On your Apple Watch, tap Settings > General > Reset > Erase All Content and Settings. This will reset your Apple Watch to the factory settings.

Have you removed/unpaired it from your old phone first?,a watch can only be paired to one phone at a time.