Apple Watch Series 2 will not pair with iPhone 11 Pro
I was able to solve the issue on my end...

Problem: new iPhone 11 pro with iOS 13 won't pair with Apple watch series 2.

So the problem was that my old iPhone 6s was on iOS v10 and watch on v3 and iPhone wouldn't upgrade my watch to the newer watch OS, probably due to OS compatibility.

Unfortunately there is no option to upgrade iPhone to version 11 or 12 - you can upgrade to the latest version only. I've took a risk and upgraded my old iPhone 6s to the latest iOS hoping that as long as it is paired with watch it would upgrade watch OS, but it didn't work out and I've got 2 phones unable to pair with my watch.

I found a friend, who was on iOS 12 and used his iPhone to pair. Before pairing it asked to upgrade watch OS (iOS 13 didn't offered this option). After upgrade watch OS I was able to pair it with any iPhone running iOS 13.

So I'm all set now.

Hopefully this info will be useful for others.