The exponent is always = -1 mod 3 since the first two terms are multiples of 3 and the last subtracts one more than a multiple of 3. 

Since the exponent = 2 mod 3, we can write the expression as 3^(3k + 2) + 4 (Without considering how to choose (n,m) to arrive at a particular k)

But 3^(3k + 2) + 4 = 3^3k * 3^2 = 9*27^k + 4. Considering this expression mod 13, we have 9^(27 mod 13 = 1)^k + 4 = 9 + 4 = 13 => Expressions of this form are always multiples of 13, and so the only way they can be prime is when the expression equals 13.

The expression is equal to 13 only when the exponent is exactly equal to 2, which gives:

3m^2 + 6n - 61 = 2

3m^2 + 6n - 63 = 0

m^2 + 2n - 21 = 0

m must be < 5 (since m,n are > 0) and must be odd since the n term is necessarily even. So m can only be 1 or 3.

(m = 1, n = 10) and (m = 3, n = 6) are therefore the only solutions.