when pairing watch get message that iphone is out of date, but it is updated

I can't successfully pair a new Apple Watch SE with my iPhone 6. I eventually get a message that my phone doesn't have the latest iOS. But when I go to updates on my phone, I do have the latest iOS installed (and automatic updates installed). How do I pair my new watch?