This is pretty late, but there is a result by Frankl and Rodl (Theorem 1.11 from http://www.renyi.hu/~pfrankl/1987-3.pdf) that shows that the graph on $\mathbb{F}_2^n$ (for $n$ a multiple of four) with vertices being adjacent if they differ in exactly $n/2$ positions has independence number at most $(2-\epsilon)^n$ for some fixed $\epsilon > 0$. Note that they describe the graph with $\pm 1$ vectors with adjacency being orthogonality, but this is equivalent. This gives an exponential lower bound for the chromatic number of this graph, and thus for the graph where adjacency is given by being different in at leat $n/2$ positions. Unfortunately this is for $k$ very far from $n$, but there may be some other useful results in that paper.

There was also a recent paper (http://arxiv.org/pdf/1608.06113v1.pdf) that proves that the orthogonal rank (smallest dimension in which vectors can be assigned such that adjacent vertices are orthogonal) of the graph on $\mathbb{F}_2^n$ with adjacency corresponding to differing in at least $n/2$ positions is exponential in $n$. The orthogonal rank lower bounds the chromatic number and their techniques could possibly be adapted for $k$ closer to $n$.

It might also be worth noting that for $k + 1 = n-1$, the chromatic number is known to be 4.

This is pretty late, but there is a result by Frankl and Rodl (Theorem 1.11 from http://www.renyi.hu/~pfrankl/1987-3.pdf) that shows that the graph on $\mathbb{F}_2^n$ (for $n$ a multiple of four) with vertices being adjacent if they differ in exactly $n/2$ positions has independence number at most $(2-\epsilon)^n$ for some fixed $\epsilon > 0$. Note that they describe the graph with $\pm 1$ vectors with adjacency being orthogonality, but this is equivalent. This gives an exponential lower bound for the chromatic number of this graph, and thus for the graph where adjacency is given by being different in at leat $n/2$ positions. Unfortunately this is for $k$ very far from $n$, but there may be some other useful results in that paper.

There was also a recent paper by Briet and Zuiddam (http://arxiv.org/pdf/1608.06113v1.pdf) that proves that the orthogonal rank (smallest dimension in which vectors can be assigned such that adjacent vertices are orthogonal) of the graph on $\mathbb{F}_2^n$ with adjacency corresponding to differing in at least $n/2$ positions is exponential in $n$. The orthogonal rank lower bounds the chromatic number and their techniques could possibly be adapted for $k$ closer to $n$.

It might also be worth noting that for $k + 1 = n-1$, the chromatic number is known to be 4.

Edit: I just looked a little more closely at the paper of Briet and Zuiddam mentioned above, and they say the best lower bound on the orthogonal rank of your $\overline{H}_n^k$ is $$2^{[1-h((k+1)/n)]n - o(n)},$$ where $h(p) = -p\log_2(p) - (1-p)\log_2(1-p)$ is the entropy of the probability distribution $(p,1-p)$. This gives an exponential lower bound on chromatic number for a fixed value of $(k+1)/n$. I think that they say that this lower bound is actually given by an unpublished paper of Samorodnitsky (http://www.cs.huji.ac.il/~salex/papers/old_sq_measure.ps).