If $\gcd(n,k)=1$ then $\gcd(n+k,k)=1$. So:
$$1\equiv (n+k)^{n+k-1}\equiv n^{n+k-1}=n^{n-1}n^k\pmod{k}$$
and hence $n^k\equiv 1\pmod{k}$ for all $n$ relatively prime to $k$.
Now if $0<n<k$ with $\gcd(n,k)=1$, then:
$$1\equiv (k-n)^{k-n-1} \equiv (-1)^{k-n-1} n^kn^{-(n-1)}n^{-2}\pmod{k}$$
But $n^k\equiv n^{-(n-1)}\equiv 1\pmod{k}$ so you have $$n^2\equiv (-1)^{k-n-1}\pmod{k}$$
That should reduce the problem greatly for case-by-case analysis. The only prime powers where every relatively prime square is $\pm 1$ are $2,4,8,3,5$. And $k$ has to be a product of these.
We know $k$ must be even, since otherwise $(2,k)=1$ and $k$ must divide $2^{2-1}-1=1$, we are most of the way.
When $k$ is even, we get that $n$ is odd, and hence $(-1)^{k-n-1}=1$ so we need $n^2\equiv 1\pmod{k}$ for all relevant $n$. But that means that $5$ can't be a factor.
This leaves us with $k=2,4,8,6,12,24$. We can quickly check each case.
Okay, more verbosely, you need to prove this lemma:
If $p^{a}\mid k$ and there is some $n_0$ such that $\gcd(n_0,p^a)=1$ and $n_0^2\not\equiv 1\pmod{p^a}$, then there is an $n$ with $\gcd(n,k)\neq 1$ such that $n^{2}\not\equiv 1\pmod{k}$.
Essentially, this is because you can write $k=p^bk'$ for $\gcd(k',p)=1$ and then solve the Chinese remainder question:
$$n\equiv n_0\pmod{p^b}\\
n\equiv 1\pmod{k'}$$
This gives you an $n$ with $n^2\not\equiv -1\pmod{p^b}$ so $n^2\not\equiv -1\pmod{k}$.