The first law could work if >>= just chose one of the values
arbitrarily. But the second law is a hopeless case. You would need to
pick one element of a pair, plug it into a function that repeats the
argument, and somehow get back the other element that you've already
dropped.
Concluding, either I'm sorely mistaken or there indeed isn't a Monad
instance for Pair.
Not quite sorely mistaken but there is a glitch in the logic of what you wrote when you returned from join to bind.
You might want to try writing out a test instance in full and re-checking the second law.