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=1}^{a-1} y_{b,2a-b} &\ge x_a\cr x_b + x_c &\le 1 + x_{(b+c)/2}\ \text{for}\ b + c\ \text{even}\cr }$$