This question is motivated by teaching : I would like to see a completely elementary proof showing for example that for all natural integers $k$ we have eventually $2^n>n^k$.

All proofs I know rely somehow on properties of the logarithm.
(I have nothing against logarithms but some students loathe them.)

*Is there a brilliant "proof from the book" for this inequality
(for example given by an explicit easy injection of a set 
containing $n^k$ elements into, say, the set of subsets of $\lbrace 1,\ldots,n\rbrace$ for $n$ sufficiently large)?*

A fairly easy but somewhat computational proof (which leaves me therefore unhappy):

Given $k$ choose $n_0>2^{k+1}$. For $n>n_0$ we have
\begin{align*}
&\frac{(n+1)^k}{2^{n+1}}\\
&=\frac{1}{2}\left(\frac{n^k}{2^n}+\frac{\sum_{j=0}^{k-1}{k\choose j}n^j}{2^n}\right)\\
&\leq \frac{n^k}{2^n}\left(\frac{1}{2}+\frac{2^k}{2n_0}\right)\\
\leq \frac{3}{4}\frac{n^k}{2^n}
\end{align*}
showing that the ratio $\frac{n^k}{2^n}$ decays exponentially fast for $n>n_0$.

A perhaps more elementary but slightly sloppy proof is the observation that digits of $n\longmapsto 2^{2^n}$ (roughly) double when increasing $n$ by $1$ whilst digits of $n\longmapsto (2^n)^k$
form (roughly) an arithmetic progression. (And this "proof" uses therefore properties of the logarithm in disguise.)

**Addendum:** Fedor Petrov's proof can be slightly rewritten as
$$2^{n+k}=\sum_j{n+k\choose j}>{n+k\choose k+1}>n^k\frac{n}{(k+1)!}$$
showing 
$$2^n>n^k\frac{n}{2^k(k+1)!}>n^k$$
for $n>2^k(k+1)!$.