If a continuous dynamical system has a constant of motion that is a function of all its variables, and is not already evidently Hamiltonian, is it always possible to use a change of variables and obtain a Hamiltonian system?
Let us reformulate OP's question as
Does a constant of motion always imply that a system has a Hamiltonian formulation (by possibly introducing additional variables)?
Answer: No. Take a system $M$ that has a constant of motion and another system $N$ that doesn't have a Hamiltonian formulation. Then the combined system $M\times N$ (where the two parts don't talk to each other) will have a constant of motion, but the full system will not have a Hamiltonian formulation.
In general, it can be hard to tell if a given set of equations of motion (eom) are part of a (possibly larger) set of eom that can be put on Hamiltonian (or on Lagrangian) form. See e.g. this and this Phys.SE post.