New Apple Watch SE won’t pair with iPhone SE 2020

They are totally compatible if the Watch is brand new not used.

What is the exact message?

First check you have no other sports watches like Fitbit that are paired to your iPhone  

Then force restart the watch. i.e. press and hold both the side button and Digital Crown for at least 10 seconds, then release both buttons when you see the Apple logo. 

Then while the watch is restarting Force Restart the iphone  

Force restart iPhone - Apple Support 

Then in the iphone, Settings, General, Transfer or reset iphone, Reset, Reset network settings. Then reconnect the iPhone to Wi-Fi.

Make sure you have no VPN or VPN based adblocker in the iphone in Settings, General, VPN & Device Management.

Then, unless your provider forbids it,  reset the router to factory settings which usually involves a paperclip on a little hole. 

Try again to pair the Watch. 

https://www.youtube.com/watch?v=e2AJa2iwEzo&pp=ygUaYXBwbGUgc3VwcG9ydCBzZXQgdXAgd2F0Y2g=

If still unsolved I recommend reviewing the steps in the articles below 

If you see 'Unable to Verify Update' when updating Apple Watch - Apple Support

If you can't pair an Apple Watch with your iPhone - Apple Support  

If your Apple Watch isn't connected or paired with your iPhone - Apple Support

LD150 wrote:

Then, unless your provider forbids it,  reset the router to factory settings which usually involves a paperclip on a little hole. 

Be careful with resetting the ADSL or other Broadband router. For some devices it is too easy to do a full Factory Reset rather than just a restart. (pull the power supply is usually good for a simple reboot on the router). Many routers have individual username and password to connect to the ISP. If these settings are lost the router will drop the connection, until the ISP's Helpdesk can guide the customer to reset them

Branta_uk wrote:

LD150 wrote:

Then, unless your provider forbids it,  reset the router to factory settings which usually involves a paperclip on a little hole. 

Be careful with resetting the ADSL or other Broadband router. For some devices it is too easy to do a full Factory Reset rather than just a restart. (pull the power supply is usually good for a simple reboot on the router). Many routers have individual username and password to connect to the ISP. If these settings are lost the router will drop the connection, until the ISP's Helpdesk can guide the customer to reset them

Unusual but possible, is why I said 'unless the provider forbids it', however doing a full factory reset is a very common remedy. I would not expect such a router to have a reset hole.

LD150 wrote:

Unusual but possible, is why I said 'unless the provider forbids it', however doing a full factory reset is a very common remedy. I would not expect such a router to have a reset hole.

Tell that to our former tech support halfwit who managed to put most of the depots off line in his efforts to get remote access over internet. Fortunately I ignored him, and our office router was tweaked to allow configuration only from inside our LAN.

eebeacon wrote:

Thank you! Yes, it seams my Fitbit was interfering… it paired fine when I ‘forgot’ the Fitbit in Bluetooth settings

Thats great, glad I could help.