I think there is some structure to your problem, but I haven't fully thought this through. For example, if $\ell$ is prime then I think $k$ must be $1$ or $\ell$. Here are some thoughts on this case. Consider the odd elements $S_{o}$ in $S$ and the even elements $S_{e}$ in $S$. Your conditions impose the restrictions that the sumsets $S_o+S_o$ and $S_e+S_e$ are both at most as big as $S$ in size. If one views these sets just in ${\Bbb Z}/\ell {\Bbb Z}$ (relations are preserved in just viewing the congruences $\pmod \ell$) then this is very close to the extremal case of the Cauchy-Davenport theorem in set addition (since one of $S_o$ or $S_e$ must contain at least half the elements in $S$). In this situation the extremal cases are well understood -- this is known as Vosper's theorem and generalizations, and you would then be able to get the structure of $S_o$ and $S_e$. Essentially they look like progressions with maybe one term omitted. (Note that Zieve's examples look like this.) So you should be able to push this through to obtain a theorem at least for $\ell$ prime. For composite $\ell$ things are more complicated since there are more subgroups, and I don't think precise extensions of Vosper's theorem are known. There is an extensive literature on such inverse problems in additive number theory, and recent work by Serra, Zemor, Hamidoune, Rodseth and many others on this topic. Let me give a pointer to http://arxiv.org/pdf/math/0507561.pdf where you will find other references; also Serra's homepage will contain other papers.
Update: As the OP pointed out my guess that when $\ell$ is prime $k$ must be $1$ or $\ell$ is not correct. What does follow from the inverse theorems referred above I think is that when $\ell$ is prime and $k<\ell$ then $S$ decomposes as the union of $S_o$ and $S_e$ and that each of these sets forms an arithmetic progression missing possibly one term.
