I will follow the steps in the document, emphasizing where the primitive root comes in.
Let $n$ be a product of two primes, say $p$ and $q$, pick $1<a<n$, and choose some $L$. The document suggests some ways to choose $L$. Take the following steps:
Compute $d_0=\gcd(a,n)$.
1.1 If $d_0>1$, we are done.
1.2 Else, continue to 2.
Compute $d_1=\gcd(a^L-1,n)$.
2.1 If $d_1=1$, then $p\not\mid a^L-1$, i.e. $a^L\not\equiv1\pmod{p}$. Choose a new $L$ and repeat.
2.2 If $1<d_1<n$, we are done.
2.3 If $d_1=n$, choose a new $a$ and repeat.
The goal is to end up in situation 2.2, so we can wonder when we do not.
Instead, we could end up in 2.1. This happens when $a^L\not\equiv1\pmod{p}$, thus when $p-1\not\mid L$. As the document states, we actually want $p-1\mid L$. This is clearly a condition on $L$, independent of $a$, so we can simply choose a new $L$ and restart.
Finally, we could end up in situation 2.3. As explained, this happens when $$a^k\equiv 1\pmod{q}$$
where $k=L\pmod{q-1}$. For which $a$'s can this happen? Well, if $k=0$, then it happens for all of them. In this case we have been quite unlucky, and choosing a new $a$ has only a very small probability of being helpful.
If $k\neq 0$, then this can not happen for all $a$'s. Remember that a primitive root $x$ modulo $q$ is defined as a non-zero integer $x$ such that $x^n\neq1\pmod{q}$ for all $0<n<q-1$. In other words, $a^k\equiv1\pmod{q}$ can only happen if $a$ is not a primitive root modulo $q$. We can choose a new $a$, and hope that the new one is a primitive root.
