I have the same problem with a Watch Series 3. Here's what worked for me. At the watch screen that shows apple watch and iPhone saying move watch close to your iPhone, I tapped the i in the bottom right corner. This took me to a screen to select language and region. I selected English and United States which is where I am. I don't know why, but it worked after that.
I think when I got the watch it was set to Japanese.