Dan, I can immediately answer two of your questions:
2) Is (*) equivalent to saying P(k) == 0 mod q has an integer solution k(q) for all prime powers q ?
Yes, by Chinese Remainder theorem. Or, more truthfully, there is a natural ring isomorphism between Z_n and the direct sum of a bunch of Z_queues. This generalises to multivariate polynomials.
3) What is known about the questions analogous to 1) and 2) for integer polynomials in 2 integer variables??? More than 2 integer variables?
In four integer variables, take the equation: P(w,x,y,z) = w^2 + x^2 + y^2 + z^2 + 1 = 0 solvable modulo every N by Lagrange's four-square theorem, but trivially not solvable in Z. I think that this trick also works for three squares (in fact it definitely does), but it miserably fails for two squares. Sincerely, Adam P. Goucher