Another counterexample - one that I should have seen right away - is the following:
Let $K$ be the field of two elements, and let $a$ be a root of $x^4+x+1=0$. In this case $E=K(a)$ is the field of 16 elements, so $Gal(E/K)$ is cyclic of order four. The Frobenius mapping $F:E\rightarrow E, x\mapsto x^2$ is a generator of the Galois group. If $H$ is the subgroup generated by $F^2$, then we run into a similar problem, because $ Tr_{E/E^H}(a)=\sum_{\sigma\in H}\sigma(a)=a+a^4=1 $ is in the prime field.
The most obvious positive result related to this question is the following. Let's make a stronger assumption that $a$ generates a normal basis of $E/K$, in other words, the set of conjugates of $a$ is a $K$-basis of $E$. In that case it is clear that $ s:=Tr_{E/E^H}(a)=\sum_{\sigma\in H}\sigma(a) $ is a fixed point of an automorphism $\tau\in Gal(E/K)$, iff $\tau\in H$, because otherwise we violate the linear independence (over $K$) of the conjugates of $a$. Thus, by Galois correspondence, the smallest extension field of $K$ containing $s$ is $K(s)=E^H.$