A finite group $G$ has two elements of the same order ; does there exists a group $H$ containing $G$ such that those elements are conjugate in $H$?

Your approach works. Say that $x$ and $y$ have order $d$. Note that if $g\in G$, then the cycle of $g$ when $x$ acts on $G$ by translation has exactly $d$ elements, namely $g,xg,x^2g,\dots,x^{d-1}g$. So all the cycles of the image of $x$ in $S_{|G|}$ have length $d$, and so the cycle structure of this image is just $|G|/d$ $d$-cycles. The same is true of $y$, so the images of $x$ and $y$ in $S_{|G|}$ are conjugate.

(Note that the hypothesis that $G$ is finite is unnecessary. This argument doesn't quite work if $G$ is countably infinite and $x$ and $y$ have infinite order, since you don't know that $x$ and $y$ must have the same number of cycles. But you can fix this by first embedding $G$ in $G\times K$ for some infinite group $K$, to ensure $x$ and $y$ each have infinitely many cycles.)

What you are looking for are HNN-extensions: introduced in a 1949 paper Embedding Theorems for Groups by Graham Higman, B. H. Neumann and Hanna Neumann, it embeds a given group $G$ into another group $H$, in such a way that two given isomorphic subgroups of $G$ are conjugate (through a given isomorphism) in $H$. Applied to your situation: $\langle x \rangle$ and $\langle y \rangle$ are isomorphic.