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.