(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 $\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(\overline{H}_n^k)$, 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(\overline{H}_n^k)$.

By the way, both $\theta$ and $\theta'$ can be computed by linear programming in this case.

(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.

Perhaps I am not saying anything new to you here, but in coding theory one is interested in upper bounds on the clique number of $\overline{H}_n^k$, as such cliques are exactly binary codes of minimal distance $k$. There is huge amount of literature on this.

And such bounds are lower bounds on $\chi(\overline{H}_n^k)$.

(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 $\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(\overline{H}_n^k)$, 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(\overline{H}_n^k)$.

By the way, both $\theta$ and $\theta'$ can be computed by linear programming in this case.