My first guess would be that if it is true, then a random subset of density $1/2$ works. A result in this direction is Lemma 3.2 in
M. Rudelson, Contact points of convex bodies, Israel Journal of Mathematics, 1997, Volume 101, Number 1, Pages 93-124
says:
Lemma :Let $x_1,...,x_k$ be vectors in $\mathbb R^n$, $\varepsilon_1,...,\varepsilon_k$ be independent Bernoulli variables, taking values $1,-1$ with probability $1/2$. Then $${\mathbb E} \left\| \sum_{i=1}^k \varepsilon_i |x_i\rangle {\langle x_i} | \right\|\leq C \log(n) \sqrt{\log(k)} \max_i \|x_i\| \left\| \sum_{i=1}^k |x_i\rangle \langle x_i| \right\|^{1/2}$$ for some absolute constant C.
In your case, this says that a random set of density $1/2$ solves the easier problem where $\delta$ may depend on $n$ and $k$. More precisely, if $ \sum_{i=1}^k |x_i\rangle \langle x_i| =1$ and $\|x_i\|< \delta$, then
$${\mathbb E} \left\|\frac12 - \sum_{i=1}^k \eta_i |x_i\rangle {\langle x_i} | \right\|\leq C/2 \log(n) \sqrt{\log(k)} \cdot \delta,$$ where $\eta_i$ are independent Bernoulli with values in $\{0,1\}$.
Since $n \leq k \delta^2$ (looking at the trace), an easy calculation shows that $\delta$ only depends on $k$. At the same time, it seems to me that the problem is getting easier if $k$ is larger, but I cannot substantiate this claim.