The problem is NP-hard by a reduction from [https://en.wikipedia.org/wiki/Independent_set_(graph_theory)](https://en.wikipedia.org/wiki/Exact_cover) or [set packing](https://en.wikipedia.org/wiki/Set_packing).

One approach to solve the problem is to use integer linear programming: define 0-or-1 variables $v_1,\dots,v_n$, and then minimize $t$ subject to the constraints $\|\sum_i v_i x_i \|_\infty \le t$ and $\sum_i v_i = k$.  Note that $\|\sum_i v_i x_i \|_\infty \le t$ iff $|\sum_i v_i x_{ij}| \le t$ for all $j$, so this can be expressed using linear constraints.  Then, apply an off-the-shelf ILP solver and hope it terminates in a reasonable amount of time.

(The ILP solver will probably apply methods such as solving the associating linear program and then applying randomized rounding, so you don't need to implement it yourself.)

If $d$ is very small, it might be possible to solve the problem in something like $\tilde{O}(dkn^{k/2})$ time using meet-in-the-middle search combined with a nearest-neighbor data structure, but I haven't worked out the details, and I expect it won't scale to large $d$.