To answer your question, yes, the Watch from T-Mobile will pair fine with your Verizon iPhone.
As stated, it's best that you use only one cellular service provider for both devices.
As a side note, unless you plan to use the watch a lot without your iPhone nearby, I've found from experience that there isn't any need for a cellular Watch. A GPS-only Watch, which is less expensive, will do everything a cellular watch will do as long as you have your iPhone with you.
Sadly, cellular service providers only sell the GPS + Cellular watch because they want you to activate the cellular service on the watch. In fact, they usually require you to use the cellular service as a condition of allowing you to buy the watch over time.