We prove that for $p\in\{1,2,\infty\}$
$$dim_{VC}\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big).$$
for the family of functions
$$A_p=\{(x,t_1,...,t_k)\mapsto1(\min_i||x-q_i||_p-t_i>0)|(x_1,...,x_k)\in(\mathbb R^d)^k\},$$
which is still bigger than the dimension of
$$B=\{(x,t)\mapsto1(\min_q||x-q_i||_p-t>0)|Q\subset\mathbb R^d, \#(Q)=k\}.$$
$$=\{(x,c_Qt)\mapsto1(c_Q\min_q||x-q_i||_p-t>0)|Q\subset\mathbb R^d, \#(Q)=k\}.$$
We note $Norm(\cdot)=||\cdot||_p$

Using $k$ clusters of $(d+1)$ points laid out in simplexes, we can find that $dim_{VC}(A_p)\geq(d+1)k$, so $d=_{k,d\to\infty}o(dim_{VC}(A_p))$. This relation will be of use later.

Consider $n$ the VC-dimension of $A_p$ and a set $x_1,...,x_n\in\mathbb R^d$ that we can pulverize. We first try to give an upper bound to the cardinal of $\big\{\{x_i\}_{1\leq i\leq n}\cap f^{-1}(\{0\})\big\}_{f\in A_p}$, then use it to derive a majoration of $n$. 

For every $1\leq i\not=j\leq n$, we can choose some hyperplane $H_{i,j}=H_{j,i}$ separating the sets $Norm(q-x_i)<Norm(q-x_j)$ and $Norm(q-x_i)>Norm(q-x_j)$. To each $q\in\mathbb R^d\setminus(\bigcup_{i,j}H_{i,j})$, associate $\sigma_q$ such that $\sigma_q(i)<\sigma_q(j)$ iff $q$ and $x_i$ are on the same side of $H_{i,j}$. If $q\in H_{i,j}$, set $\sigma_q$ to be the permutation of a neighbouring region of $\mathbb R^d\setminus(\bigcup_{i,j}H_{i,j})$. 

If we note $N=\frac{n(n-1)}2$ the number of hyperplanes, $\mathbb R^d\setminus(\bigcup_{i,j}H_{i,j})$ has at most $P_d(N)=\dbinom{N+1}{0}+\dbinom{N+1}{1}+...+\dbinom{N+1}{d}$ open regions. Note that $P_n$ is of degree $d$. For $k$ and $d$ going to $\infty$, we have $d=_{d,k\to\infty}o(dk)=_{d,k\to\infty}o(N)$, so we should have $P_d(N)\sim_{k,d\to\infty}\binom{N+1}d\frac{((N+1)/d-0.5)^de^d}{\sqrt{2\pi k}}.$ Without proof of the former, let us use the much coarser $P_d(N)\leq (d+1)\binom{N+1}d$.

For every $q\in\mathbb R^d$, $Norm(q-x_{\sigma_q(i)})$ is non decreasing, so when we picking a radius $t$, the ball of center $q$ and radius $t$ can have at most $n+1$ intersections with $\{x_1,...,x_n\}$ : no points, $\{x_{\sigma_q(1)}\}$, $\{x_{\sigma_q(1)},x_{\sigma_q(2)}\}$,... or all the $x_i$. For a ball of center $q_i$ and radius $t_i$, choosing $q_i$ gives at most $P_d(N)$ possibilities for $\sigma_q$, wich then translates to at most $(n+1)P_d(N)$ possibilities for $B(q_i,t_i)\cap\{x_i\}_{i\leq n}$. With $k$ balls, we get $\big((n+1)P_d(N)\big)^k$ possible sets.

Since we can pulverize $x_1,...,x_n$, we have
\begin{align*}
2^n&\leq\big((n+1)P_d(N)\big)^k\\
n\ln(2)&\leq k\ln\big((n+1)P_d(\frac{n(n-1)}2)\big)\\
n&\leq \frac{k}{\ln(2)}\ln\left((n+1)(d+1)\binom{N}{d}\right)\\
&\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( k\ln(nd\frac{(\frac{N}d-\frac12)^d\mathrm e^d}{\sqrt d})\Big)\\
&\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( k\big(\ln(n)+\ln(d)+d\ln(\frac{N}d-\frac12)+d-\frac12\ln(d)\big)\Big)\\
&\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(\frac{N}d)\Big)\\
&\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(n)\Big)\\
&\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk\ln(n))\Big)\\
&\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big)+O\Big(dk\ln(\ln(n))\Big)\\
&\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big)+o\Big(dk\ln(n)\Big)\\
&\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big)
\end{align*}
For $k,d\to\infty$, we used an equivalent for $\binom{N}k$ when $k=o(N)$, and used the fact that $\ln(N)=O( \ln(n))$.
Using the better equivalent $P_d(N)\sim\binom{N+1}d$ (if true) should provide $O(dk\ln(k)).$