Let G be a simple graph where all the vertices have degree at least $(1-\frac 1r + \frac{\varepsilon}{2})n$, where $n$ is the number of vertices and $\varepsilon >0, r \geq 1$.
I want to prove that there are at least $ (\frac {r \varepsilon n}2)^{r+1}$ copies of the complete graph $K_{r+1}$ in G.
The proof is hinted to rely on a greedy algorithm, and on the observation that every $r$ vertices have at least $\frac {r\varepsilon n}2 $ common neighbors.
I managed to prove the observation by counting: Given vertices $v_1,...,v_r$, we know each of them has at least $\frac {r-1}rn + \frac{\varepsilon}{2}n$ neighbors, and so the sum of the degrees is at least $(r-1)n+\frac {r \varepsilon n}2$, so by the pigeonhole principle at least $\frac {r \varepsilon n}2$ vertices occur more than $r-1$ times, as desired. (We note that the $v_i$ themselves cannot occur more than $r-1$ times, so these are indeed common neighbors.)
As for the algorithm, for every $r$ vertices one can find $\frac {r\varepsilon n}2 $ additional vertices that complete them to a $K_{r+1}$. That way we find $\frac {r\varepsilon n}2 {n \choose r}$ copies of $K_{r+1}$, and we count every copy $r+1$ times so we found $\frac{\frac {r\varepsilon n}2 {n \choose r}}{r+1}$ distinct copies, but this is not what we need to prove.
Your proof of the observation is correct.
This is not necessarily, because even the induced subgraph on these $r$ vertices may be not $K_r$.
We can prove an inequality a (bit) weaker than the required as follows. For each $1\le d\le r+1$ by $N_d$ we denote the number of copies of the complete graph $K_d$ in $G$. Remark that if $d\le r$ then since, as you already proved, any $d$ vertices have at least $M=\frac{r\varepsilon n}2$ common neighbors, each copy of $K_d$ belongs to at least $M$ copies of $K_{d+1}$. Thus $N_d\le N_{d+1}(d+1)/M$. Therefore $$N_{r+1}\ge N_1 M^{r}=\frac{nM^r}{(r+1)!}.$$