Bounds on the size of NFA for $r$-skip $k$-distinct language
I detail the comment below, as you could be interested in this answer.
I don't know about NFA, but if your goal is to represent this language with a small automaton,  you could use the model of alternating automata, or AFA.

Intuitively, DFA are with $0$ player: the run is updated automatically, NFA are with $1$ player who has to choose a good run, and AFA are played by two players: one tries to accept, the other to reject. The word is in the language if the "good" player (who wants to accept) has a winning strategy on this word. This does not increase the expressive power of automata.

Here, you have an AFA with essentially $kr (\log n)^k$ states: 
At one point the opposite player can guess that some letter with same position modulo $r$ will be equal to the current one.
Then the "good" player guesses $k$ bit positions of the current letter (this requires $(\log n)^k$ memory) : one which will be different for each later equivalent position. Then we just have to check that one of these bits is indeed different every $r$ positions.