Let $\chi_X:\{-1,1\}^n\to \{0,1\}$ be the characteristic function of a subset $X\subseteq \{-1,1\}^n$, which is randomly drawn from all subsets with exactly $k$ elements.
Is the support of the Fourier transform (Walsh-Hadamard transform) $\hat{\chi}_X$ large ($\geq c2^n$ for a constant $c>0$) with high probability?
Impose any bijection $\pi:u\mapsto t$ between the sets $\{\pm 1\}^n$ and $\{0,1,\ldots,2^n-1\}$ so that you can write the derived binary function $$f_X:\{0,\ldots,2^n-1\}\rightarrow \{0,1\},$$ via $$ f_X(t)=\chi_X(\pi^{-1}(t)).$$
Rueppel (R. A. Rueppel. Analysis and Design of Stream Ciphers Springer-Verlag, 1986, Chapter 4) has shown that when we consider all binary sequences of period $N$ under the uniform probability distribution, the expected linear complexity is $N/2,$ with a small variance, see for example this paper. Here we have $N=2^n.$ Linear complexity of a sequence is the length of the shortest linear feedback shift register that will generate it and it can be computed via the recursive Berlekamp-Massey algorithm.
Blahut's theorem (google it) states that the linear complexity of a binary sequence is equal to the Hamming weight (number of nonzero coefficients) of its Fourier/Hadamard transform.
Certainly if $k$ is near $N/2$ the lower bound of the form you want holds for some $c>0.$
If $k$ is near $N,$ or near zero, we can use the idea of $k-$ error linear complexity to relate the linear complexity of the given sequence to that of the constant (either all zero or all 1) sequence. There are some recent bounds on the $k-$error linear complexity. See for example this paper which may help you obtain some bounds.
