Assume $p \in \mathbb P.$ Assume $0<p-2k<p$ and the next square larger than $p(p-2k)$ is $(p-k)^2$.
It is trivial to show that $p(p-2k)+k^2$ is a square. Simply $p(p-2k)+k^2 = (p-k)^2.$ Starting with $k = 1$ we get next square larger than $p(p-2k)$ is $(p-k)^2$ and the distance to it is $k^2$.
However, at some point this fails to be true. For example, take $p = 41$. Then $41(41-2*8) + 8^2 = 33^2$ and similarly for all $k$ smaller than 8. But $41(41-2*9) = 943$ and $943 + 9^2 = 32^2 > 31^2 = 943 + 18$. Thus the next square larger than $41(41-2*9)$ is not $(41-9)^2$.
Note also that the distance of $943$ to the true next square is not a square itself, unlike it was for smaller $k$.
I would like to prove that $\forall \, p>2, \, p \in \mathbb P$ the largest $a, \, 0<a<p$ for which the distance to the next square larger than $a p$ is a square itself is $(p-2k)$ where $k$ is the largest such number that the true next square of $p(p-2k)$ is $(p-k)^2$.
As for why I think this would be the case. If $a$ is as described, we get $$a p + k^2 = (p-2k)n+k^2 = p^2 - 2k p + k^2 = (p-k)^2.$$ Thus $$a p = (p-k)^2-k^2.$$ Then note that $$a p = a^2 \left( \left(\frac{p-k}{a} \right)^2 - \left(\frac{k}{a}\right)^2 \right)$$ and so $$\frac{p-k+k}{\gcd(p,a)} = p$$ and $$\frac{p-2 k}{\gcd(p-2 k,a)} = 1.$$ As expected, we get only the two trivial divisors. I have a suspicion that if we could find $a$ which didn't fulfill the condition I wish to prove, it would lead to us discovering nontrivial divisors of $p$, which is impossible. But I would like some ideas or a possible counterexample, than you.
The title of the question comes from the fact that if the distance to next square larger than $p(p-2k)$ is $k^2$ then $(p-k) = \lceil \sqrt{(p-2k) p} \rceil$. The distance to the next largest square is $\lceil \sqrt{(p-2k) p} \rceil^2-(p-2k) p$ and this has to be $k^2$, so $$k^2-(\lceil \sqrt{(p-2k) p} \rceil^2-(p-2k))=(p-k)^2-\lceil \sqrt{(p-2k) p} \rceil^2 = 0$$ and thus $$(p-k)=\lceil \sqrt{(p-2k) p} \rceil$$
Find $k$ so that $p-k-1\geq\sqrt{p(p-2k)}$. So $$(p-(k+1))^2 \geq p^2-2k$$ or $$p-2pk -2p + (k+1)^2\geq p^2-2pk$$
Thus $(k+1)^2\geq 2p$. So when $k\geq \sqrt{2p}-1$, you fail to have the given equality, and if $k<\sqrt{2p}-1$ you do.
So the answer to the title question is $k=\lceil \sqrt{2p}-2\rceil$.
You definitely don't need the fact that $p$ is prime, only that it is an integer $p\geq 2$.