nt.number theory - Finite set of (perfect power) polynomial values?

As Qiaochu said in the comments, you must include Pell type equations as a special case, because they are the only counter example. At least for $k=2$, Siegel's theorem on integral points on algebraic curves implies that if your polynomial $P(x)$ has at least three distinct roots then $P(n)=m^2$ has only finitely many solutions. So your conjecture is, in particular, true for irreducible polynomials of degree higher than 2.

Anyway, for the general question for any exponent it's better that you read the full story in
"The diophantine equation f(x)=g(y)" by Y. Bilu and R.F. Tichy.