Not an answer, but a method how to find some "good" $k$ (and perhaps this is how you found $k=1805$).
Suppose that for some $m$ we already know that $$\tag1n^n+k\text{ is prime}\implies m\mid n.$$
Let $q$ be a prime divisor of $k+1$ and suppose that $q-1\mid m$ and $q\nmid m$. Then $n^n+k$ can only be prime if $q\mid n$. Indeed, in all other cases we have (as we can assume $q-1\mid m\mid n$) $$n^n=\left(n^{q-1}\right)^{\frac n{q-1}}\equiv 1\pmod q$$
and so $q\mid n^n+k$. Thus except in the trivial case $k=q-1$, $n=1$, we see that $n^n+k$ is not prime. It follows that in $(1)$, we can replace $m$ with $qm$.
Initially, $(1)$ holds for $m=1$, no matter what $k$ we use. Hence if $k+1$ is even, we can use the above to improve this to $m=2$. Then with $q=3$, we can improve this to $m=6$ as long as $k\equiv -1\pmod 6$. Next we can use $q=7$ to improve this to $m=42$ provided $k\equiv -1\pmod{42}$. Then using $q=43$ to $m=1806$ provided $k\equiv -1\pmod {1806}$. Unfortunately, $1807=13\cdot 139$ is not prime and in fact there is no additional prime $q$ with $q-1\mid 1806$. Interestingly, we have reconstructed the finite OEIS sequence A014117 along the way. But it seems that $k=1805$ is the largest $k$ for which we can easily show that $(1)$ holds with $m=k+1$.