Diagonalization of Hessian H= PkP$^{-1}$: what do the elements of P matrix physically mean?
Are the $q$s in $\mathbf{P}$ coordinates of the atoms in molecules? 


Close, but not quite. The $q_{i,j}$ represent the displacements from the equilibrium geometry of the appropriate atom/coordinate $i$, for each mode j. Thus, for example, $q_{5,9}$ corresponds to the displacement from equilibrium of atom $2$ along axis $2$ (typically the $y$-axis) when the molecule is undergoing vibration in mode $9$.


  If so, aren't they always changing since they are vibrating, rotating...?


There are no changes due to translation or rotation. It is customary to "project out" the translational and rotational motion from the Hessian and the geometry.  Qualitatively, this means that we simply ignore the translation and rotation and consider the molecule as "fixed" in its equilibrium configuration (allowing for vibrational 'wiggling'), with that configuration always oriented in the same way relative to the coordinate system.

As for the vibrational motion, though: yes, the $q_{i,j}$ values do technically also 'wiggle' as the molecule vibrates. However, the magnitudes of the perturbations $\delta q_{i,j}$ are in many cases very small, and can be neglected. In those cases where they cannot, the harmonic oscillator approximation to the vibrational motion breaks down and is no longer a useful model for vibration along that mode.

See my answers here and here for some links to literature on situations where this occurs (emphasis on the 'internal rotation' topics, though some of the 'anharmonic' and 'Coriolis' references might be somewhat relevant). Here is a Chem.SE question about nitrogen inversion that might be of interest.  More generally, a Google search for "low-frequency vibrational modes" should turn up lots of interesting reading.