For any particular $k$ and $l$, you can express your constraints in terms of binary integer programming and search for solutions using software such as Cplex.
Thus let $x_i = 1$ if $i \in S$, $0$ otherwise, and $y_{ij} = 1$ if $\{i,j\} \subseteq S$, $0$ otherwise.  You have constraints

$$\eqalign{\sum_i x_i &= k \cr
y_{ij} &\ge x_i + x_j - 1\cr
y_{ij} &\le x_i \cr
y_{ij} &\le x_j \cr
x_a + x_{a+l} &\le 1 \ \text{for}\ a < l\cr
\sum_{b} y_{b,2a-b} &\ge x_a\cr
x_b + x_c &\le 1 + x_{(b+c)/2} + x_{(b+c)/2\pm l}\ \text{for}\ b + c\ \text{even}\cr
}$$