Theorem. There is $P$ for which the reachability problem in your first question is NP hard.
Proof. Suppose we have any NP decision problem $A$, where for any string $a$, we have $a\in A$ if and only if there is a string $b$ of the same length such that a fixed polynomial time program $p$ accepts $(a,b)$ (this form is achievable without loss of generality by padding). Consider now the following algorithm $P$. On strings of the form $(a,x)$, where $x$ has the same length a $a$, our algorithm checks if $p$ accepts $(a,x)$, and if so, outputs a default accepting output. Otherwise, our algorithm outputs $(a,x^+)$, where $x^+$ is the lexicographic successor to $x$ in the space of all strings of that length, unless $x$ was already the lexically maximal string of that length, in which case $P$ outputs a default rejecting output. This program is polynomial time computable, since it takes just a little longer than $p$ does. But notice that iterating $P$ has the effect of searching through the exponential-size space of witnesses. In particular, if $\vec 0$ is the lexically least string, then $(a,\vec 0)$ reaches the default accepting output if and only if there is a witness for $a$, if and only if $a\in A$. So we have reduced $A$ to your problem for this $P$, and so if $A$ is NP-complete, your problem is NP hard. QED
Meanwhile, I don't expect that your problem is always in NP itself, since it seems that one can use exponential size iterations, in the way I just did, and I don't see how to have a polynomial size witness to reachability. (Meanwhile, the reachability problem for some other $P$ can of course be trivial.)
A similar idea shows more:
Theorem. There are $P$ for which your reachability problem is PSPACE complete.
Proof. First, let's show that it can be PSPACE hard. Given any program $p$, such that $p(a)$ runs in polynomial space, design a program $P$ to computer from input of the form $(a,c)$, where $c$ is a string that will be regarded as encoding the configuration during the computation of $p(a)$, of the right length for the bounded on the space needed by $p(a)$. Our program $P$ will perform one step of the computation of $p(a)$ by moving $c$ to the next configuration $c^+$ that would arise during the computation of $p$, or a default accepting or rejecting string if $p(a)$ should halt right at this step of computation. Thus, iterating $P$ corresponds to undertaking the computation of $p(a)$. Therefore, we can reduce the question about whether $p$ accepts or rejects $a$ to the question of whether a certain string is reachable from $(a,c_0)$, where $c_0$ is the starting configuration for $p(a)$. So every PSPACE decidable question reduces to one of your reachability decision problems, and so by using a PSPACE complete $p$, we see that one of your decision problems is PSPACE hard.
Finally, we show that all your reachability problems are themselves in PSPACE. To see if $B$ is reachable from $A$ via $P$, we simply compute successive iterates $P^k(A)$, while at the same time incrementing a counter to count up to the total number of strings of that length (as in the NP argument above). We can do this in polynomial space. If we find that $B$ is reached, then we accept. If the counter runs out and we did not reach $B$, then since we iterated long enough, we know $B$ is not reachable and so we may confidently reject.
So we have PSPACE completeness. QED
