Here are asymptotic bounds for $k(n, m)$ that are tight up to a logarithmic factor.
Note the threshold around $m = \Theta(n^{3/2})$:
Theorem 1.
$~~~~\frac{1}{21}\min(\lceil\sqrt n\rceil, \lceil m/(n\log n)\rceil)
~\le~
k(n, m) ~\le ~\min(\sqrt {n}, 2\lceil m/n\rceil).$
Here's the proof. We show the upper bounds (Lemma 1) then the lower bounds (Lemma 2).
Lemma 1. $k(n, m) \le \min(\sqrt {n}, 2\lceil m/n\rceil)$
Proof. First we show $k(n, m) \le \sqrt n$.
Partition the vertex greedily into some $p$ parts of size at most $\sqrt n/2$. Then, for each of the ${p\choose 2} \le n$ unordered pairs $\{A, B\}$ of distinct parts, create a vertex set $S_i$ consisting of $A\cup B$ (having size at most $\sqrt n$). There are at most $n$ such pairs $\{A, B\}$, and every edge has both endpoints in $A\cup B$ for some pair. This shows $k(n, m) \le \sqrt n$.
To finish we show $k(n, m) \le 2\lceil m/n\rceil$.
Greedily partition the edge set $E$ into $n$ sets $E_1, \ldots, E_n$
such that each contains at most $\lceil m/n\rceil$ edges.
For each $i\in [n]$, let $S_i$ be the set of vertices used in edge set $E_i$.
Then $|S_i| \le 2 |E_i| \le 2\lceil m/n\rceil$, as desired.$~~~~\Box$
Here is the lower bound.
Lemma 2. $k(n, m) \ge \min(\sqrt n, \lceil m/(n\ln n)\rceil)/21$
Proof.
Let $m' = n^{3/2}\ln n$.
The lower bound (of $\sqrt n/21$) for $m\ge m'$ follows from the lower bound for $m=m'$.
And a lower bound of $1$ holds trivially for all positive $m \le n\ln n$.
So assume without loss of generality that $n\ln n \le m \le n^{3/2}\ln n$.
Let $k=k(n, m)$ and $p = m/n^2$.
Let $G=(V, E)$ be a random graph where each edge is independently present with probability $p$.
Claim 1: With probability $1-o(1)$ $G$ has the following two properties:
$m/3 = p n^2/3 \le |E| \le p n^2 = m$
For every vertex subset $S\subseteq V$ of size $k$,
we have $|E_S| \le 7 k \ln n$,
where $E_S$ denotes the set of edges with both endpoints in $S$.
Suppose the claim is true. Let $G$ have these two properties.
By definition of $k$ there are $n$ $k$-vertex induced subgraphs in $G$ that collectively contain all of $G$'s edges.
By Property 2, each of these $n$ subgraphs contains at most $7 k \ln n$ edges from $S$,
so collectively they contain at most $7 n k \ln n$ edges.
But they contain $E$, and (by Property 1) $|E|\ge m/3$.
So $7 n k \ln n \ge m/3$. Simplifying implies $k \ge m/(21 n \ln n)$, as desired.
To complete the proof we show the claim.
The expected number of edges in $G$ is ${n\choose 2}p \sim n^2p/2$.
By a standard Chernoff bound the probability
that $n^2p/3 \le |E| \le n^2 p$ fails to hold is at most $2\exp(-\Omega(n^2 p))$, which (by the choice of $p$) is $o(1)$.
So Property 1 fails with probability $o(1)$.
The number of $k$-vertex subgraphs of $G$ is ${n\choose k} \le n^k$.
For each, (using $k \le n^{1/2}$ and $m\le n^{3/2}\ln n$)
its expected number of edges is
${k \choose 2} p \le 3.5 k \ln n$,
so by a standard Chernoff bound the probability that the number is more than $2\times 3.5 k\ln n$ is at most
$\exp(-3.5 k\ln (n)/3) \le \exp(-1.1 k \ln n)$.
So by the naive union bound the probability that Property 2 fails is at most
$n^k \exp(-1.1 k\ln n) = \exp(-0.1 k\ln n) = o(1).$
So Property 2 fails with probability $o(1)$.
By the naive union bound, the probability that either Property 1 or Property 2 fails is $o(1)$.
This proves the claim, and the lemma. $~~~~\Box$
