Let $G=(n,p)$ with $p \ll n^{-1+\epsilon}$ for all $\epsilon >0$. Then for each $k\in \mathbb{N}$ there are a.a.s no $k$ vertices with at least $k+1$ edges.
Proof: We want to show $$\Pr(\exists S\subseteq V: |S|=k, |E_S|\geq k+1) \to 0\quad (n\to \infty).$$
Let $S\subseteq V$ with $|S|=k$. Then there are ${k}\choose{2}$$=\frac{k(k-1)}{2}$ possible subsets with 2 elements. Lets call them $A_i$, Define the random varibles $1_{A_i}$ such that $$1_{A_i}=1 \text{ when } A_i \subset{E_S},\quad 0 \text{ else}$$
We have $$\Pr(|S|=k, |E_S|\geq k+1)=\Pr(\sum_i 1_{A_i} \geq k+1)\leq \frac{E\sum_i 1_{A_i}}{k+1}$$
Then $E\sum_i 1_{A_i}=\frac{k(k-1)}{2}\Pr(1_{A_i}=1)=\frac{k(k-1)}{2}p$ since the probability of the edges is independent.
Now we have $$\Pr(|S|=k, |E_S|\geq k+1)=\Pr(\sum_i 1_{A_i} \geq k+1)\leq \frac{E\sum_i 1_{A_i}}{k-1}<\frac{k}{2}p \ll \frac{k}{2} \frac{1}{nn^{-\epsilon}}$$
Now pick: $n^{\epsilon}=k$. is this correct? does the result follow?
The approach you have taken is not strong enough to get the desired conclusion.
The use of $1_{A_i}$ is a bit strange, but everything you've done can be phrased in terms of the random variable $|E_S|$ (for a fixed $S$). You are applying Markov's inequality to $|E_S|$, saying that $$ \Pr[|E_S| \ge k+1] \le \frac{\mathbb E[|E_S|]}{k+1}. $$ By linearity of expectation, $\mathbb E[|E_S|] = \binom k2 p$. It is not quite correct that $\binom k2 = \frac{k(k+1)}{2}$; rather, $\binom k2 = \frac{k(k-1)}{2}$. But this is not important, since we still have $\frac{\binom k2 p}{k+1} < \frac {kp}{2} \ll \frac{k}{n^{1-\epsilon}}$.
Here, $k = |S| \le n$, and this inequality is potentially strong enough to prove that for any given $S$, we have $|E_S| \le |S|$ with high probability. But that's not what we want: we want a result that holds for all $S$.
Consider $k=4$, for example: then there are $\binom n4$ sets $S$ we could consider, and if the probability is $\ll \frac{4}{n^{1-\epsilon}}$ for each one, that only tells us that the expected number of sets $S$ with $5$ edges is $\ll \binom n4 \frac{4}{n^{1-\epsilon}}$ or in other words it is $\ll n^{3+\epsilon}$, which still could be very large.
We can improve on Markov's inequality for bounding the probability that a set $S$ induces a subgraph we don't like.
First of all: for any $k$, there is only a constant number of $k$-vertex graphs with $k+1$ edges. So if we show that for a fixed graph $H$ (on $k$ vertices and with $k+1$ edges) the random graph doesn't have an $H$-subgraph a.a.s., then we immediately conclude that the random graph doesn't have any such subgraphs with $k$ vertices and $k+1$ edges a.a.s. (Since the subgraphs are not necessarily induced, this also rules out subgraphs with $k$ vertices and more than $k+1$ edges.)
As an upper bound, the expected number of labeled $H$-subgraphs in $\mathcal G_{n,p}$ is less than $n^{|V(H)|}p^{|E(H)|}$. (The power of $n$ is actually at most $n(n-1)(n-2)\dotsb$ with $|V(H)|$ factors.) If $H$ has $k$ vertices and $k+1$ edges, this is $n^k p^{k+1}$.
We have $p \ll n^{-1+\epsilon}$ for all $\epsilon>0$, so in particular, $p \ll n^{-1 + \frac{1}{k+1}}$. Therefore $p^{k+1} \ll n^{-k}$, and $n^k p^{k+1} \to 0$ as $n \to \infty$. Therefore $\mathcal G_{n,p}$ has no copies of $H$ a.a.s., and by doing this for every $k$-vertex graph with $k+1$ edges we get the statement you want.
A subtle point here is that we are proving the statement "for each $k$, a.a.s., $\mathcal G_{n,p}$ contains no $k$-vertex subgraph with at least $k+1$ edges" not "a.a.s., $\mathcal G_{n,p}$ contains no $k$-vertex subgraph with at least $k+1$ edges for each $k$". That is, $k$ is a constant fixed outside the limit as $n \to \infty$.
If we didn't do this, then the statement would not be true, because $\mathcal G_{n,p}$ for $p \gg \frac1n$ does contain large subgraphs with more edges than vertices (in particular, the whole graph is such a subgraph).