Suppose there is a root $x \in \Bbb F_{q^n}$ of this polynomial for some $n$. Then, since $x \neq 0$ and $x^p = 1$, $\Bbb F_{q^n}^\times$ contains a cyclic group of order $p$, so its order, $q^n-1$, has to be divisible by $p$.
Since you supposed that $q$ was a primitive root of $\Bbb F_p^\times$, $q^n \equiv 1 \pmod p \iff n \equiv 0 \pmod {p-1}$.
This shows that if $x$ is a root of this polynomial then it lives in an extension of $\Bbb F_{q^{p-1}}$. Since the polynomial is of degree $p-1$, it is irreducible.
Let $L$ be the splitting field and $\alpha \in L$ a root. Consider the map $Gal(L/F) \to \mathbb Z/p\mathbb Z$ given by $\sigma \mapsto \sigma(\alpha)-\alpha$ (You should verify that this is well defined). Since $\mathbb Z/p\mathbb Z$ has no non-trivial subgroups, the map is either trivial or surjective. If the map is surjective, we deduce that the galois group acts transitively on the roots, hence the polynomial is irreducible. If the map is trivial, we deduce $\alpha \in F$, which is a contradiction to the assumption.
Without Galois theory (but somehow the same proof): Consider the isomorphism $\varphi: F[x]\to F[x], x \mapsto x+1$. The polynomial $f = x^p-x-c$ is fixed by $\varphi$, hence the irreducible factors are permuted by $\varphi$. Let the irreducible factors be $M := \{f_1, \dotsc, f_n \}$. Since there is no root in $F$, we have $n < p$.
$\langle \varphi \rangle \cong \mathbb Z/p\mathbb Z$ acts on $M$, hence we get a homomorphism $\langle \varphi \rangle \cong \mathbb Z/p\mathbb Z \to S_n$. From $n<p$ we deduce that this homomorphism is trivial, hence the action is trivial, so all irreducible factors are fixed by $\varphi$. You should finish the proof by showing that $\varphi$ does not fix any polynomials of degree $1, 2 ,\dotsc, p-1$. Hence the only irreducible factor can be $f$ itself.
Best Answer
If you meant $a \in \mathbb{F}_p^*$ then this answers the question.
Let $g(x) =x^p-x = \prod_{n \in \mathbb{F}_p} (x-n)$. For any $m \in \mathbb{F}_p$ : $g(m) = 0$. Take $a \in \mathbb{F}_p^*$. Then $f(x) = g(x)-a$ has no roots in $\mathbb{F}_p$.
Let $\beta$ be one of its root in $\mathbb{F}_{p^k}$ the splitting field of $f$. Since $g(\beta+n) = g(\beta)$, the other roots of $f$ are $\beta+n,n \in \mathbb{F}_p$.
Thus, $\sigma \in Gal(\mathbb{F}_{p^k}/\mathbb{F}_{p})$ sends $\beta$ to $\beta+n$. Since $f$ doesn't split completely in $\mathbb{F}_p$ we can choose $\sigma$ such that $\sigma(\beta) \ne \beta$ so that $n\ne 0$. Therefore $n$ generates $(\mathbb{F}_p,+)$ and the iterates of $\sigma$ act transitively on the roots of $f$, which means $f$ is irreducible over $\mathbb{F}_p$.
All this to say $\mathbb{F}_p(\beta)=\mathbb{F}_p[x]/(f(x))= \mathbb{F}_{p^{\,p}}$ which is the splitting field of $f$.
Since $p$ is prime, there is no subfield between $\mathbb{F}_p$ and $\mathbb{F}_{p^{\,p}}$, and hence there are two possible cases if $K$ is an extension of $\mathbb{F}_p$ :
Or $\mathbb{F}_{p^p} \subseteq K$ and $f$ splits completely over $K$,
Or $\mathbb{F}_{p^p} \not\subseteq K$ and $f$ is irreducible over $K$.
If you meant $a \in K^*$ is algebraic over $\mathbb{F}_p$ then it depends on $f$ having a root in $\mathbb{F}_p(a)=\mathbb{F}_{p^N}$ or not. If it has no root, repeat the same argument with $\sigma \in Gal(\mathbb{F}_{p^{N}}(\beta)/\mathbb{F}_{p^N})$. You get again that the $p$ roots of $f$ are $\beta+n$ and the iterates of $\sigma$ act transively on those, therefore $f$ is irreducible over $\mathbb{F}_{p^N}$ and splits completely in $\mathbb{F}_{p^{N}}(\beta) = \mathbb{F}_{p^{N}}|x]/(f(x))=\mathbb{F}_{p^{pN}}$. Again $[\mathbb{F}_{p^{pN}}:\mathbb{F}_{p^{N}}]= p$ is prime so there are no subfield between the two, and there are two possible cases if $K$ is an extension of $\mathbb{F}_p(a)=\mathbb{F}_{p^{N}} $ :
Or $\mathbb{F}_{p^{pN}} \subseteq K$ and $f$ splits completely over $K$,
Or $\mathbb{F}_{p^{pN}} \not\subseteq K$ and $f$ is irreducible over $K$.