I don't see what Cayley's theorem has to do with anything; it gives you an embedding of your group into some symmetric group, but gives you no guarantees of that being the smallest symmetric group.
In stead, a quick check will show that $S_n$ has no elements of order $5$ for $n<5$. And you have found a subgroup of order $5$ in $S_5$, hence $n=5$ is the smallest $n$ for which such a subgroup exists. Done.
You neither necessarily have an isomorphism to $S_n$, nor do you necessarily have $H=H_G$.
I am only guessing that the proof you found says the set of symmetries of $\{gH\mid g\in G\}$ is isomorphic to $S_n$, not that the map gives an isomorphism. The notation
$$\pi\colon G/\mathrm{core}(H) \to \mathrm{Sym}(\{gH\mid g\in G\})\cong S_n$$
does not say $\pi$ is an isomorphism, it says that
$$\mathrm{Sym}(\{gH\mid g\in G\})$$
is isomorphic to $S_n$. And this follows because the set has $n=[G:H]$ elements.
If they had meant to say that $\pi$ is an isomorphism, they would probably have written:
$$\pi \colon G/H_G \stackrel{\cong}{\to} \mathrm{Sym}(\{gH\mid g\in G\})\cong S_n$$
which they do not do. So they are not saying that $\pi$ is an isomorphism between $G/H_G$ and $S_n$.
It also does say that $H_G$ equals $H$. But the map factors through $G/H_G$. To see that this is the kernel, note first that the kernel is certainly normal. And if $x$ lies in the kernel, then for every $g\in G$ you have that $x(gH) = gH$.
In particular, $xH=H$, so $x\in H$. This proves the kernel is normal and contained in $H$, hence contained in $H_G$.
Conversely, if $x\in H_G$, then for every $g\in G$ we have $x\in gHg^{-1}$, hence $g^{-1}xg\in H$. Therefore, $g^{-1}xgH = H$, and so $xgH = gH$. That means that $x(gH) = gH$, so the action of $x$ on the cosets of $H$ is trivial, so $\pi(x)$ is the identity; that is, $x\in\mathrm{ker}(\pi)$. This vies the other inclusion and hence equality.
Best Answer
Here's an informal argument:
You want to show that $G$ is isomorphic to a subgroup of $S_n$ (for $n=\vert G\vert$). Well, how do you show that something is isomorphic to a subgroup of $S_n$? Actions! Elements of $S_n$ are understood by how they permute the set $[n]=\{1, 2, . . . , n\}$. So in order to show that $G$ is isomorphic to a subgroup of $S_n$, what we need is a machine for doing the following:
Take in a $g\in G$.
Spit out a permutation $\pi_g\in S_n$.
The hope is that the map $h: G\rightarrow S_n: g\mapsto \pi_g$ will be a homomorphism from $G$ to $S_n$, and that it will be injective; then $G$ will be isomorphic to $im(h)$.
So this boils down to:
This is hard because $G$ is an abstract group - we have no sense of what $G$ is "meant to do." So we have to cook up some interpretation of $G$ from scratch!
Luckily, there is a natural $n$-element set lying around: $G$ itself! So, is there a way we can think of an element of $G$ permuting the whole set $G$?
The answer is: yes! Given an element $g$, consider the map from $G$ to $G$ defined as $$\pi_g: a\mapsto g\cdot a.$$ Each $\pi_g$ is a permutation of $G$, we have $\pi_g=\pi_h$ iff $g=h$, and $\pi_g\circ \pi_h=\pi_{gh}$ (do you see why these facts are true?); so the map $h: g\mapsto \pi_g$ is in fact an injective group homomorphism from $G$ to the group of permutations of $G$ . . .
. . . but this latter group is just $S_n$, renamed!