Embedding of group such that two elements of same order become conjugate

Actually, after thinking a bit more on it, this turns out to follow from the proof of Cayley's theorem. By construction, the embedding in that sends an element of order $m$ to a product of disjoint $m$-cycles (since this is the action by left translation), so all elements of the same order become conjugate.

The answer is yes. As Tobias Kildetoft indicated in the comments, in the regular representation of $G$ all non-identity elements act fixed point freely. So the two elements of the same order $n$ both consist of $|G|/n$ cycles of length $n$, and hence they are conjugate in the symmetric group on the elements of $G$.

More generally, if $A$ and $B$ are isomorphic subgroups of a finite group $G$ and $\phi:A \to B$ is an isomorphism, then you can embed $G$ in a finite group $X$ with an element $g \in X$ such that $g^{-1}ag=\phi(a)$ for all $a \in A$. This is a result of B.H. Neumann - I was looking for the original reference but I haven;t found it yet - he wrote several papers on similar themes.