Efficiently finding key sets
Your problem is discussed in the paper Efficient construction of a small hitting set for combinatorial rectangles in high dimension by Linial, Luby, Saks and Zuckerman. The object you're after is called a $(2,n,2^{-k})$-hitting set in the paper (this notation is not standard). They construct such a set of size $\mathrm{poly}(2^k\log n)$ in time $\mathrm{poly}(2^k n)$, and give a lower bound of $\Omega(2^{k+1} + \log n)$. Their construction certainly doesn't produce a minimal hitting set, and they're not necessarily interested in your range of parameters, but perhaps you could chase the literature from there on and find more relevant material.