J, 2626 23 bytes
Returns the first n pairs.
{.&(/:^/&>)&,[:<@,"0/~2+i{@;~2+i.
2+i.
Integers from 2 to n+1.
<@,"0/~{@;~
Table of all pairs of these integers.
(/:^/&>)&,
Flatten into a list of pairs and sort by the value of the exponentiation.
{.
Take the first n pairs.