I have the same problem. Just factory reset the watch, but now it shows the pairing code, yet the phone doesn't. Sometimes, after the pairing fails, a code will pop up on the phone, but it's the wrong code.
Phone Hardware: HTC One Max (stock, latest Sprint firmware), all apps updated.