Finding irreducible polynomials over GF(2) with the fewest terms
According to a paper "Optimal Irreducible Polynomials for $GF(2^m)$ Arithmetic" by M. Scott, "it is in practise always possible to chooose as an irreducible polynomial either a trinomial... or a pentanomial." [talk slides] [PDF link]
In random number generators irreducible trinomials of various degrees with three nonzero binary coefficients are associated with the names Tausworthe-Lewis-Payne.
Added: It has been known since Gauss that there are lots of irreducible polynomials over a finite field, basically the analog of the Prime Number Theorem for such polynomials. Among the $2^m$ (monic) polynomials over Z/2Z of degree $m$, approximately $1/m$ of them are irreducible.
We can eliminate the possibility of first degree factors by inspection, for divisibility by $x$ or $x+1$ would imply respectively a zero constant term or an even number of nonzero terms in the polynomial. So the first case to test for irreducibility is the trinomials of degree $m$. With leading and constant coefficients accounting for two of the three nonzero terms, there are but $m-1$ possibilities to test, and by symmetry of $x$ → $1/x$ substitution, we can restrict the middle terms to degree ≤ $m/2$.
If none of those pan out, we have the richer supply of pentanomials to test. Indeed you seem to have hit upon a seam of cases where trinomials will never work out, namely degree $m$ a multiple of 8 [PS] (Swan, 1962).
The work then comes down to testing all the $\binom{m-1}{3}$ binary pentanomials $p(x)$ until we find one that's irreducible. Your application might make other conditions, perhaps similar to those considered in Scott's paper above, attractive. Given the modest degrees you are working with, trial division (taking $p(x) \; mod \; q(x)$ for all $q(x)$ of degree ≤ $m/2$) should be fast enough. [Remember, we shouldn't have to test more than O(m) possibilities before we find success.]
There is a fancier way [PDF] to test polynomials for irreducibility over GF(2). A necessary condition for binary polynomial $p(x)$ to be irreducible over $GF(2)$ is that:
$$x^{2^m} = x \mod p(x)$$
In fact Gauss showed for prime q that $x^{q^m} - x$ is precisely the product of all monic irreducible polynomials over $GF(q)$ whose degrees divide $m$. [From this he deduced the count of monic irreducible polynomials of degree exactly $m$ is asymptotically $q^m/m$ as $m \rightarrow \infty$.]
For $q = 2$ it follows that if $p(x)$ is irreducible of degree $m$, it divides $x^{2^m} - x$ over $GF(2)$, i.e. the congruence above.
Rubin (1980) proposed a necessary and sufficient test for irreducibility, combining the above with some additional steps to rule out the possibility that $p(x)$ might be the product of some irreducible factors whose degrees properly divide $m$. [While the degrees of the irreducible factors would naturally sum to $m$, having all the irreducible factors' degrees divide $m$ would be somewhat special, unless of course there is only one factor.]
The additional "sufficiency" steps are to check for each prime factor $d_i$ of $m$ that: $$GCD(x^{2^{m/d}} - x, p(x)) = 1$$
That is, if $p(x)$ were to have an irreducible factor of degree $k$ properly dividing $m$, it would crop up when taking the gcd of $x^{2^{m/d}} - x$ and $p(x)$ if $k$ divides $m/d$.
Since then a lot of ingenuity has been applied to efficiently doing these steps. Of course the necessary condition lends itself to repeated squaring, computing $x^{2^{k+1}} = (x^{2^k})^2$ mod $p(x)$, for $k$ up to $m-1$. We can take advantage here of the fact that the multiplication we're doing is a squaring and advantage of the sparsity of our $p(x)$ as a pentanomial when doing reduction mod $p(x)$.
As the report by Brent of work with Zimmerman (linked above) points out, this repeated squaring gives with each (fairly inexpensive step) linear progress toward the "exponent of the exponent" $m$. There is also a way to progress farther with greater computational effort by modular composition.
That is, suppose we've already arrived at: $$f(x) = x^{2^k} \mod p(x)$$ and $$g(x) = x^{2^j} \mod p(x)$$ Then: $$f(g(x)) = x^{2^{k+j}} \mod p(x)$$
Thus composition of two polynomials $f(x)$ and $g(x)$ mod $p(x)$ can replace a number of repeated squaring steps. But composition mod $p(x)$ is more expensive than squaring or even than multiplication generally mod $p(x)$. So as Brent points out, practical advantage for using modular composition lies at the final stage(s) of evaluating the necessary condition. E.g. at the end one modular composition might replace $m/2$ repeated squarings.
As far as the "sufficiency" conditions go, Gao and Panario outlined an improvement over a naive implementation of Rubin's tests in this 1997 paper [PDF], basically sequencing the gcd computations in an expedient order.