Since my original posting some ten days ago, I discovered an amazing example which changed significantly my perception of the problem. Accordingly, the whole post got re-written now.

The most general form of the question I am interested in is as follows: Given integers $n\ge k\ge 1$ and $N\le 2^n$, for a collection of $N$ Hamming spheres in ${\mathbb F}_2^n$ of radius $1$, what is the smallest possible number of points in ${\mathbb F}_2^n$ covered by at least $k$ spheres?

Denote by $F_0$ the set of all even-weight points of ${\mathbb F}_2^n$, and suppose that all our spheres are centered at the points of $F_0$. (The motivation here is that even-centered and odd-centered spheres are disjoint; hence, the sets they $k$-cover are disjoint, too.) It is not difficult to find a linear subspace $L < F_0$ of co-dimension $\lceil \log_2 n/(k-1) \rceil$ such that no point in ${\mathbb F}_2^n$ is covered by $k$ (or more) spheres, centered at the elements of $L$. Therefore, if the number of spheres is $N\lesssim2^{n-1}k/n$, then the set of $k$-covered points can be empty. On the other hand, by a simple double counting, for any system of $N$ even-centered spheres, the number of $k$-covered points is at least $$ \Big(1-\frac{2^{n-1}k}{nN}\Big) \, N. $$ To what extent can this trivial estimate be improved, assuming that $N$ is reasonably large (say, $N>2^{n-2}$)? Is it true, for instance, that the number of $k$-covered points is at least $N$? Here is a rather surprising construction which places some limits on what one can expect in this direction.

Suppose that $n=(k+1)2^k$. Partition the index set $[n]$ into a union
$I_1\cup\dotsb\cup I_{2^k}$, with every set $I_s$ of size $k+1$, and let
$B$ denote the set of all those points $(x_1,\ldots,x_n)\in{\mathbb F}_2^n$ such
that for each $I_s$, there is an index $i\in I_s$ with $x_i=1$. (Loosely
speaking, $B$ consists of all those vectors which do not vanish on any of
the coordinate blocks determined by the sets $I_s$.) Next, let $C:=B\cap
F_0$ and consider the system of $N:=|C|$ unit spheres, centered at the
points of $C$. An easy computation confirms that $N>2^{n-2}$, and the
number of odd points in $B$ is exactly $N-1$. Furthermore, every odd
point in $B$ is covered by lots of spheres (at least $k2^k$ of them),
while every odd point *not* in $B$ is covered by at most $k+1\le\log_2 n$
spheres. Thus, we have just $N-1$ points, covered by "really many"
spheres.

Another example to keep in mind: fix $I\subset[n]$ with $|I|=k$, let $B$
consist of all vectors $(x_1,\ldots,x_n)\in{\mathbb F}_2^n$ such that there exists
$i\in I$ with $x_i=1$, and consider the system of $N=(1-2^{-k})2^{n-1}$
unit spheres centered at the points of the set $C:=B\cap F_0$. There are
exactly $N$ odd points in $B$, and every odd point *not* in $B$ is
covered by only $k$ spheres. Therefore, we have $N$ points covered by
many spheres, whereas all other points are covered by a very small number
of spheres (for $k$ small).

These constructions suggest two questions.

Is it true that for any collection of $N>2^{n-2}$ even-centered unit spheres in ${\mathbb F}_2^n$, there are at least $N-1$ points, covered by $cn$ or more spheres (for some absolute constant $c>0$)?

Is it true that for any collection of $N>2^{n-2}$ even-centered unit spheres in ${\mathbb F}_2^n$, there are at least $N$ points, covered by $c\log n$ or more spheres (for some absolute constant $c>0$)?

Here lies an argument showing that there are at least $N$ points, covered by two or more spheres. Unfortunately, this argument does not seem to extend onto three or more spheres.

A curious observation is that if $C$ and $\overline C$ are complementary subsets of $F_0$, and $S$ is the set of all points $k$-covered by the spheres centered at the elements of $C$, then the set of all points $(n-k)$-covered by the spheres centered at the elements of $\overline C$ is exactly the set of all odd points not in $S$. This allows one to equivalently restate the two questions above; say, the first of them gets the following shape:

Is it true that for any collection of $N<2^{n-2}$ even-centered unit spheres in ${\mathbb F}_2^n$, there are at most $N+1$ points, covered by $(1-c)n$ or more spheres (for some absolute constant $c>0$)?

Hamming balls. I am not sure of what exactly you mean by the problem of "bounding the size of multi-covering codes". It is quite possible that my question is related to some known coding-theory problems (and hence one of the tags); practically, I don't know of any such problem. – Seva Dec 23 '11 at 8:15