"smallest" irreducible polynomial over GF(p) Let $n = 2^{e_0} q_1^{e_1} \cdots q_i^{e_i}$ be the prime factorization of $n$.
Let $p$ be an odd prime.
Is it true that: $\exists k$ such that $x^n+k$ is irreducible over GF($p$) $\iff$ $(2^{\min(e_0,2)}q_1 \cdots q_i) | (p-1)$ ?
Are there similar criteria for "larger" polynomials such as $x^n+k_1x+k_0$ ?
 A: The $\Leftarrow$-direction of the first question is answered in the affirmative with the aid of LTE, the Lifting-the-exponent Lemma.

Let $u$ be a primitive root modulo $p$. That is, an element of order $p-1$ in the multiplicative group of $GF(p)$. I claim that $f(x)=x^n-u$ is irreducible in $GF(p)[x]$.

This is seen as follows. Let $\alpha$ be a zero of $f(x)$ in some extension field $K$ of $GF(p)$. We can assume that $K=GF(p)(\alpha)$. Furthermore, $|K|=p^m$ where $m$ is the degree of the minimal polynomial of $\alpha$. Because every prime factor of $p-1$ is also a factor of $n$, we can immediately conclude that the order of $\alpha$ in $K^*$ is $n(p-1)$. Therefore $n(p-1)$ is a factor of $p^m-1$.
Let $q$ be one of the odd prime factors of $n$ and let $q^e$ be the (highest) power $q$ that appears in the factorization of $n$. We know that $q\mid p-1$. So LTE says that
$$
\nu_q(p^m-1)=\nu_q(p-1)+\nu_q(m).
$$
On the other hand
$$\nu_q(n(p-1))=\nu_q(p-1)+\nu_q(n)=\nu_q(p-1)+e.$$
As $n(p-1)\mid p^m-1$ we can deduce that $\nu_q(m)\ge e$. In other words, $m$ must be divisible by $q^e$.
We still need to deal with the even prime. If $4\mid n$, your condition conveniently implies that we also have $4\mid p-1$. This is just what the doctor ordered for LTE to bite! We can, again,
deduce that
$$
\nu_2(p^m-1)=\nu_2(p-1)+\nu_2(m)
$$
as well as
$$
\nu_2(n(p-1))=\nu_2(p-1)+e_0.
$$
Again, the conclusion is that $2^{e_0}\mid m$. Lastly, if $n\equiv2\pmod 4$ then we need $(p^m-1)/(p-1)=1+p+p^2+\cdots+p^{m-1}$ to be even. This is the case if and only if $m$ is even, so even in this case we have $2^{e_0}\mid m$.
We have proven that $m$ must be divisible $n$. But $m\le\deg f(x)= n$. Therefore $m=n$, and $f(x)$ must be that minimal polynomial. Hence it is irreducible.

The $\Rightarrow$-direction:
Assume that there is an odd prime $q$ such that $q\mid n$, $q\nmid p-1$. As $GF(p)^*$ is cyclic of order $p-1$, the latter assumption means that every element $k\in GF(p)$ is a $q$th power of some element of $GF(p)$, say $k=a^q$.
Then
$$
x^n+k=(x^{n/q})^q+a^q=(x^{n/q}+a)\sum_{j=0}^{q-1}(-1)^jx^{jn/q}a^{q-1-j}
$$
so it cannot be irreducible.
If $4\mid n$ and $4\nmid p-1$, then it is also impossible for $x^n+k$ to be irreducible. If $k$ is a square in $GF(p)$ so is $k/4$. As $\gcd(4,p-1)=2$,
every square is also a fourth power, so $k/4=a^4$ for some $a\in GF(p)$. We get
a Sophie Germain style factorization from
$$
\begin{aligned}
x^n+k=x^n+4a^4&=(x^n+4a^2x^{n/2}+4a^4)-4a^2x^{n/2}\\
&=(x^{n/2}+2a^2)^2-(2ax^{n/4})^2.
\end{aligned}
$$
If $k$ is a non-square, then $-k$ is a square. If $k=-a^2$, we have the obvious
$$
x^n+k=x^n-a^2=(x^{n/2}-a)(x^{n/2}+a).
$$
