Another way to state your condition is that, for every $\beta \in \mathbf{F}_{2^k}$, $f(\beta)$ has trace 0 over $\mathbf{F}_2$.
For $k=5$, an example is $f(x) = x^9 - x^5$. To see that this has trace 0 for any $\beta \in \mathbf{F}_{32}$:
$ \begin{align*} \mathop{Tr}(\beta^9 - \beta^5) &= \mathop{Tr}(\beta^9) - \mathop{Tr}(\beta^5) \\&= (\beta^9 + \beta^{18} + \beta^{36} + \beta^{72} + \beta^{144}) - (\beta^5 + \beta^{10} + \beta^{20} + \beta^{40} + \beta^{80}) \\&= (\beta^9 + \beta^{18} + \beta^{5} + \beta^{10} + \beta^{20}) - (\beta^5 + \beta^{10} + \beta^{20} + \beta^{9} + \beta^{18}) \\&= 0 \end{align*} $
In general, the condition means that
$ f(\beta) + f(\beta)^2 + \cdots + f(\beta)^{2^{k-1}} = 0 $
for every $\beta \in \mathbf{F}_{2^k}$, or equivalently,
$ f(x) + f^\sigma(x^2) + f^{\sigma^2}(x^4) + \cdots + f^{\sigma^{k-1}}(x^{2^{k-1}}) \equiv 0 \pmod{ x^{2^k} - x} $
where $f^\sigma$ is the polynomial formed by conjugating each coefficient of $f$ by the action $u \mapsto u^2$.
We can split the powers of $x$ into orbits under the action $x \mapsto x^2 \pmod{x^{2^k} - x}$ -- i.e. writing
$ f(x) = u + h(x) (x^{2^k} - x) + \sum_m g_m(x^m) $
where $u$ is a constant with trace 0, and each $g$ has the form
$g(x) = \sum_{j=0}^{k-1} c_j x^{2^j}.$
Each $g(x)$ must satisfy the constraint, and any choice of valid $g's$ gives a valid $f$. So,
$0 \equiv \sum_{i=0}^{k-1} g^{\sigma^i}(x^{2^i}) \equiv \sum_{i=0}^{k-1} \sum_{j=0}^{k-1} c_j^{2^i} x^{2^{i+j}} = \sum_{j=0}^{k-1} x^{2^{j}} \sum_{i=0}^{k-1} c_{j-i}^{2^{i}} \pmod{x^{2^k} - x} $
(there was a change of variable $j \mapsto j-i$) where the index on $c$ is taken modulo $k$. Each coefficient gives the same condition:
$\sum_{i=0}^{k-1} c_{k-1-i}^{2^i} = 0$
Now, how can we use this to find a polynomial of small, odd degree? Consider $k=5$. One of the orbits of powers of x is:
$ x^5, x^{10}, x^{20}, x^{40} \equiv x^9, x^{80} \equiv x^{18} $
By setting the coefficients on $x^9$ and a smaller term to $1$ and the rest to $0$ will satisfy the equation. This is the example at the top of my answer.