A prime dividing both numbers forces the order of $2$ modulo that prime to divide $2m$ and $n$ but not $m$

The gcd exceeds $1$ exactly when $n$ contains strictly more factors of $2$ than $m;$ count pairs by the power of $2$ in each number

Suppose an odd prime $p$ divides both $2^m + 1$ and $2^n - 1.$ From $2^m \equiv -1 \pmod p,$ the order of $2$ modulo $p$ divides $2m$ but not $m,$ so the order contains exactly one more factor of $2$ than $m$ does. The order also divides $n,$ so $n$ must contain strictly more factors of $2$ than $m:$ writing $v_2$ for the number of factors of $2,$ we need $v_2(n) \gt v_2(m).$

Conversely, if $v_2(n) \gt v_2(m),$ let $g = \gcd(m, n).$ Then $v_2(g) = v_2(m),$ so $\frac{m}{g}$ is odd and $2^g + 1$ divides $2^m + 1;$ also $2g$ divides $n,$ so $2^g + 1$ divides $2^{2g} - 1,$ which in turn divides $2^n - 1.$ Hence the gcd exceeds $1$ exactly when $v_2(n) \gt v_2(m).$

Among $1, \ldots, 30$ the counts of numbers with $v_2 = 0, 1, 2, 3, 4$ are $15, 8, 4, 2, 1.$ The number of pairs with $v_2(m) \lt v_2(n)$ is $$\begin{aligned} &15 \cdot 15 + 8 \cdot 7 + 4 \cdot 3 + 2 \cdot 1 \\ &= 225 + 56 + 12 + 2 = 295. \end{aligned}$$