Why is the set of NFA that accept all words in co-NPSPACE?

In Sipser's book there is a section describing how to decide

$\qquad\displaystyle \mathrm{ALL}_\mathrm{NFA} = \{ \langle N \rangle \mid N \text{ is an NFA}, L(N) = \Sigma^*\}$

in polynomial space. To do so, it shows $\overline{\mathrm{ALL}_\mathrm{NFA} }$ is in NPSPACE.

I don't understand this part: If $M$, the NTM deciding the language, rejects any strings, it must reject one of length at most $ 2^q $ where $q$ is the number of states in $M$. For any longer string that is rejected, some states would repeat. But why? Is there any alternative explanation that helps in understanding this part?

Your question is really about the following statement: If an NFA with $n$ states does not accept every string, then it rejects some string of length at most $2^n$. (The rest of the proof comes from the fact that REACH is in NL.)

To see why this is so, first let's look at a DFA with $k$ states that does not accept every string. The transition function of the DFA corresponds to a directed graph $G$ on $k$ vertices. DFA computations bijectively correspond to walks in $G$ starting from the vertex $s$ representing the start state.

Since the DFA does not accept every string, there is a vertex representing a non-accepting state $j$ reachable by a walk from $s$. In particular, there is a simple path $P$ from $s$ to $j$, which can have length at most $k$ (e.g., DFS will produce one). $P$ corresponds to a string of length at most $k$ that is not accepted.

The NFA question reduces to the DFA one. Using the powerset construction, convert the NFA with $n$ states to a DFA with $k = 2^n$ states and then use the above argument.

StackExchange Computer Science Q#24390, answer score: 5