Filling bins with pairs of balls
TL;DR -- No, there is no better strategy than the simple strategy.  Here is the main idea of the proof. When there are not enough balls, there will be a "ball path" from a $k$-full bin to a bin with at most $k-2$ balls. The adversary can pass a ball from that full bin to that less full bin along that path, which can be done repeatedly until the number of $k$-full bins is reduced.




Reformulation in Graph theory

Suppose we are given a simple finite graph $G(V,E)$ with a function $w: E\to\Bbb Z_{\ge 0}$. We say there are $w(e)$ balls in edge $e$. Let $E_2$ be the (end-marked edge) set $\{(e,v)| e\in E, v\in e\}$. If $d:E_2\to\Bbb Z_{\ge 0}$ satisfies $w(e)=d(e,v_1) + d(e,v_2)$ for every edge $e=\{v_1,v_2\}$, we say that $d$ is $w$-distributing. Any $w$-distributing function $d$ induces a function, which we use the same symbol, $d:V\to\Bbb Z_{\ge 0}$, $d(v) =\sum_{v\in e}d(e,v)$. We say that $d(v)$ balls are in $v$. Given $k\in\Bbb Z_{\gt0}$, let $F_k(d)=\#\{v\in V|d(v)\ge k\}$, the number of $k$-full vertices by $d$.

(Erel-Apass Theorem) For any simple finite graph $G(V,E)$ and $w:E\to\Bbb Z_{\ge0}$, we have $\sum_{e\in E}w(e)\geq (2k-1) \min_{w\text{-distributing }d}F_k(d)$

Imagine each vertex is a bin. For each edge $e=\{v_1,v_2\}$, $w(e)$ ball-pairs are put into $v_1$ and $v_2$, each of which getting $w(e)$ balls. Among these $w(e)$ ball-pairs, the adversary may take away $d(e,v_2)$ balls from $v_1$ and $d(e,v_1)$ balls from $v_2$. The end result is the same as if, given all empty bins initially, for each edge $e=\{v_1, v_2\}$, $w(e)$ balls are put into it and, then, $d(e,v_1)$ and $d(e,v_2)$ balls are distributed to $v_1$ and $v_2$ respectively by the adversary.  Hence, Erel-Apass theorem says that in order to ensure $t$ k-full bins after a smart adversary's removal, at least $(2k-1)t$ pairs of balls are needed. In another word, an optimal strategy to have the maximum possible number of full bins left is indeed the "simple strategy", which repeatedly fills a different pair of bins with $2k-1$ ball-pairs until we do not have enough balls to repeat.



Proof of the theorem

For the sake of contradiction, let $G(V,E)$ and $w$ be a counterexample whose number of vertices is the smallest among all counterexamples. That is, there is $w$-distributing $m$ such that $F_k(m)$ is minimal among all $F_k(d)$ of $w$-distributing function $d$. Furthermore,
$$\sum_{e\in E}w(e)\lt (2k-1)F_k(m)$$

Let $V_s=\{v\in V | m(v)\le k-2\}$. Let $V_\ell=\{v\in V|m(v)\geq k\}$. So $F_k(m)=\#V_\ell$.

Claim one: $V_s\neq\emptyset$.
Proof of claim one. Suppose otherwise that $V_s$ is empty.
$$ \sum_{v\in V}m(v)= (k-1)\#V +\sum_{v\in V}(m(v)-(k-1))
                    \ge (k-1)\#V + \#V_\ell \gt (k-1)\#V$$
Let us also reuse $w$ as a function from $V$ to $\Bbb Z_{\ge 0}$ such that $w(v)=\sum_{v\in e}w(e)$ for any $v\in V$.
$$\begin{align}
\sum_{v\in V}w(v) &amp;=\sum_{v\in V}\sum_{v\in e }w(e) 
                  =\sum_{e\in E }\sum_{v\in e}w(e) 
                  =\sum_{e\in E}2w(e)
                  =2\sum_{e\in E}w(e)\\
                  &amp;=2\sum_{e\in E }\sum_{v\in e}m(e,v)
                  =2\sum_{v\in V}\sum_{v\in e }m(e,v)
                  =2\sum_{v\in V}m(v)\\
                  &amp;\gt 2(k-1)\#V
\end{align}$$
So there must be a vertex $b$ such that $w(b)\ge 2k-1$.

Consider the induced setup $G'(V', E')$ and $w'$, where $V'=V\setminus\{b\}$, $G'(V', E')$ is the induced graph $G[V']$ and where $w'=w|_{E'}$. For any $w'$-distributing function $d'$, we can extend it to a $w$-distributing function $d_{d'}$ where $d_{d'}$ is the same as $d'$ on $E'$ while $d_{d'}(e, b)=w(e)$ for every edge $e$ adjacent to $b$. Note that $F_k(d_{d'})= F_k(d') + 1$ since $d_{d'}(b)=\sum_{b\in e}d_{d'}(e,b) = \sum_{b\in e}w(e)=w(b)\ge 2k-1\ge k$. Then
$$\begin{align}\sum_{e\in E'}w'(e)&amp;\le\sum_{e\in E}w(e) - w(b)\\
  &amp;\lt (2k-1)F_k(m) -(2k-1)\\
  &amp;=(2k-1) \left(\min_{w\text{-distributing }d}F_k(d) -1\right)\\
  &amp;\le (2k-1) \left(\min_{w'\text{-distributing }d'}F_k(d_{d'})-1\right)\\
  &amp;\le (2k-1) \min_{w'\text{-distributing }d'}F_k(d')
\end{align}$$
So, $G'(V', E')$ and $w'$ is a counterexample whose number of vertices is smaller than the number of vertices in $G$. That cannot true by our assumption about $G(V,E)$ and $w$. So claim one is proved.



For any vertex $v$, define $v$ $d$-reachable from vertex $u$ if there is a path $u_0= u, u_1, u_2, \cdots, u_m, u_{m+1}=v$, $m\ge0$ such that $d(\{u_i, u_{i+1}\}, u_i)&gt;0$. Let $V_r=V_\ell\cup \{v\in V|\exists u\in V_\ell \text{ and } v\text{ is } m\text{-reachable from } u \}$.

Claim two: $V_r = V$
Proof of claim two: Suppose $V_r\neq V$. For any vertex $v\in V_r$ and $u\notin V_r$, since we cannot reach $u$ from $v$,  if $\{v, u\}$ is an edge, then $w(\{v, u\}, v) = 0.$ Consider the induced setup $G'(V', E')$ and $w'$, where $v'=V_r$, $G'(V', E')$ is the induced graph $G[V']$ and where $w'=w|_{E'}$. For any $w'$-distributing function $d'$, we can extend it to a $w$-distributing function $d_{d'}$ where $d_{d'}$ is the same as $d'$ on $E'$ and the same as $m$ on other edges. Note that $F_k(d_{d'})= F_k(d')$ since all vertices with no less than $k$ balls inside are in $V_\ell\subset V_r$. Then
$$\begin{align}\sum_{e\in E'}w'(e)&amp;\le\sum_{e\in E}w(e)\\
  &amp;\lt (2k-1)F_k(m)\\
  &amp;=(2k-1) \min_{w\text{-distributing }d}F_k(d)\\
  &amp;\le (2k-1) \min_{w'\text{-distributing }d'}F_k(d_{d'})\\
  &amp;\le (2k-1) \min_{w'\text{-distributing }d'}F_k(d')
\end{align}$$
So, $G'(V', E')$ and $w'$ would be a counterexample whose number of vertices is smaller than the number of vertices in $G$. That cannot be true by our assumption about $G(V,E)$ and $w$. So claim two is proved.



Now let us prove the theorem.

Since $V_r=V$ and $V_s\neq\emptyset$, there is a path $u_0= u, u_1, u_2, \cdots, u_m, u_{m+1}=v$, $m\ge0$ with $m(u)\gt k$, $m(v)\leq k-2$ and $d(\{u_i, u_{i+1}\}, u_i)&gt;0$. Let us construct a new $w$-distributing function $r(m)$ from $m$ so that
$$r(m)(e, u)= \begin{cases}
    m(\{u_i, u_{i+1}\}, u_i) -1 &amp; \text{ if } (e,u)=(\{u_i, u_{i+1}\},u_i)\text { for some } 0\le i\le m\\
    m(\{u_i, u_{i+1}\}, u_{i+1}) +1 &amp; \text{ if } (e,u)=(\{u_i, u_{i+1}\},u_{i+1})\text { for some } 0\le i\le m\\
    m(e,u) &amp;\text{ otherwise }
  \end{cases}$$

$m$ and $r(m)$ agrees on all vertices except $v$ and $u$, $m(v)\lt r(m)(v)\le k-1$ and $r(m)(u)\lt m(u)$. We can apply this procedure on $r(m)$ to get $r^2(m)$. Repeating this $i$ time for some large enough $i$, we will obtain a $w$-distributing function $r^i(m)$ with $F_k(r^i(m))=0$. However, we have assumed that $F_k(m)&gt;0$ is the minimum among $F(d)$ of $w$-distributing function $d$. This contradiction shows that we have proved the Erel-Apass theorem.