(Edited after it was pointed out that the original answer made no sense).
In coding theory one is interested in upper bounds on the clique number $\omega$ of $\Gamma:=\overline{H}_n^k$, as such cliques are exactly binary codes of minimal distance $k$. There is huge amount of literature on this. The Delsarte bound, also known as Schrijver's $\theta'$ (see his paper called "Comparison of Delsarte and Lovasz bounds" from 1979), is particularly interesting, as it is known to be "sandwiched" between $\omega$ and $\chi:=\chi(\Gamma)$, i.e. $\omega\leq\theta'\leq\theta\leq\chi$, where $\theta$ is Lovasz's $\theta$ function of the graph. (More precisely, $\theta$ and $\theta'$ are usually defined for the complement of the graph, but that's a minor notational issue).
And so $\theta$ and $\theta'$ are lower bounds on $\chi(\Gamma)$.
By the way, both $\theta$ and $\theta'$ can be computed by linear programming in this case.
ADDED:
In a nutshell, $\theta$ and $\theta'$ can be described for this case as follows. Let $A_m$ denote the adjacency matrix of the graph on the $n$-binary words, vertices adjacent iff the corr. words are at Hamming distance $m$. E.g. the adjacency matrix of $\Gamma$ equals $\sum_{m\geq k} A_m$
Let $v$ be the $0-1$ indicator vector of a clique in $\Gamma$. Then one can computed the Frobenius scalar product of $vv^\top$ and each $A_k$, and it stays the same if we replace $vv^\top$ by its average $V$ over the group of automorphisms of the Hamming space. Now, $V$ can also be written as a linear combination of $A_m$'s. Thinking of $V$ as an unknown positive semidefinite matrix, one thinks of the latter expression with unknown coefficients $x_m$, and the clique size is an linear function $f(x)$ in $x_m$. The matrices $A_m$ commute with each other, so we can simultaneously diagonalize them. As a result we get a system of inequalities (and thus a linear program with the objective function $f(x)$) with $x_m$'s variables, from the fact that the eigenvalues of $V$ are nonnegative.
There are variations as to whether to demand $x_m\geq 0$ or not, this gives one $\theta'$, resp. $\theta$, as the optimum of the linear program I just mentioned.