Why are there infinitely many positive $k$ such that $\lfloor \frac{n^k}{k}\rfloor$ is odd?

If $n$ is odd, take $k=n^s$ ($s=1,2,3,\dots$).

If $n$ is even and $n>2$, choose any prime divisor $p$ of $n-1$ and take $k=p^s$ (the trick is that $n^{p^s}-1$ is divisible by $p^s$, which is easy to show by induction).

Finally, consider the case $n=2$. Here I do not know a really nice proof but the following argument works. Take $k=2^sp$ where $p$ is an odd prime. Then $2^k-2^{2^s}$ is divisible by $2^sp$ and the quotient is even if $s$ is not too small, so we just want to make $[2^{2^s-s}/p]$ odd, which can be achieved by taking for $p$ any prime divisor of $2^{2^s-s}-1$.