Let the maximum length sequence $$s_n=(-1)^{Tr(\beta \alpha^n)}$$have period $2^m-1,$ and be nontrivial with $\beta\neq0.$ Your sum is $$\sum_{n=1}^N s_n \exp(2 \pi i n/N).$$
If $\beta=0,$ you have the standard unmodulated linear exponential sum with the bound $$\min\left\{N,\frac{1}{|\sin \pi/N|}\right\}. $$
If $N\leq m,$ all possible $N-$tuples in $\{\pm 1\}^N$ are taken on by $$(s_n,\ldots,s_{n+N-1})$$ so a better bound is not possible.
In the intermediate range $m<N\leq 2^m-1,$ maybe a bound along the lines suggested by @FelipeVoloch is possible, I am not sure.