When the electrostatic force was originally being studied, force, mass, distance and time were all fairly well understood, but the electrostatic force and electric charge were new and exotic. In the cgs system, the charge was defined in relation to the resulting electrostatic force (it's called a Franklin (Fr) an "electrostatic unit" (esu or) sometimes a statCoulomb (statC)).
In that system, we express the force on one charged particle by another as $F_E=\frac{q_1 q_2}{r^2}$ where the unit of charge is the esu, the unit of force is the dyne and the unit of distance is the centimeter. In the MKS system (now called SI), we would write $F_E = k_e\frac{q_1 q_2}{r^2}$ where the unit of charge is the coulomb, the unit of force is the newton, and the unit of distance the meter. It would seem that if things are equivalent, then $k_e$ is indeed just a conversion factor, but things are definitely not equivalent.
A little history is probably useful at this point. In 1873, when the cgs system was first standardized, it finally made a clear distinction between mass and force. Before that, it was common to express both in terms of the same unit, such as the pound. So if you think of it, people still say things like "I weigh 72 kg" rather than "I weigh 705 N here on the surface of Earth" and they also say $1 \mathrm { kg} = 2.2\mathrm{ lb}$ confusing mass and weight (the cgs Imperial unit of mass is actually the slug).
This is important, because there is a direct analogy to the issue of units of charge and to your question about the units of $k_e$. The Franklin is defined as "that charge which exerts on an equal charge at a distance of one centimeter in vacuo a force of one dyne." The value of $k_e$ is assumed to be 1 and is dimensionless in the cgs system.
In cgs, the unit of charge, therefore, already implictly has this value of $k_e$ built in. However in the SI units, they started with Amperes and derived Coulombs from that and time ($C=It$). The resulting units of $k_e$ are a result of that choice.
So although the physical phenomenon is the same, it is the choice of units that either gives $k_e$ dimension or not.
See this paper for perhaps a little more detail on how this works in practice.
A specific parameter might correspond to a specific (SI) unit, but not all units correspond to a specific parameter!
Kinetic energy is
$$\begin{align}
K&=\frac{1}{2} mv^2 \\
[\text{Joules}]&=\frac{1}{2}[ \text{kilograms}\times\text{meters}^2/\text{seconds}^2]
\end{align}$$
We also have gravitational potential energy:
$$\begin{align}U&=mgh \\
[\text{Joules}] &= [\text{kilograms} \times(\text{meters} / \text{seconds}^2) \times \text{meters}]\\
&= [\text{kilograms} \times \text{meters}^2 / \text{seconds}^2]
\end{align}$$
So, is Joules both $\frac{1}{2} \text{kilograms}\times\text{meters}^2/\text{seconds}^2$ and $ \text{kilograms}\times\text{meters}^2/\text{seconds}^2$ at the same time? If you have a value in Joules and you need to find the number of kilograms, then how would you go backwards? How would you do the algebra?
You could start from any of these unit-formulations, and you would get difference answers for the number of kilograms. The answer is not unique seen from the units since the original formula could have contained unit-less parameters.
The problem is that there are many kinds of energy with the same unit. In general, parameters have unique units, but units don't belong to unique parameters. You cannot go "backwards" from the unit formulation of a formula.
Best Answer
Well, the way to find the units of the constant are to consider the equation it takes part in:
$$ F = G\frac{m_1 m_2}{r^2} $$
$F$ is a force: so it's measured in newtons ($\operatorname{N}$). A newton is the force required to give a kilogram an acceleration of a metre per second per second: so, in SI units, its units are $\operatorname{kg}\operatorname{m}/\operatorname{s}^2$. $m_1$ and $m_2$ are masses: in SI units they are measured in kilograms, $\operatorname{kg}$, and $r$ is a length: it is measured in metres, $\operatorname{m}$.
So, again in SI units we can rewrite the above as something like
$$\phi \operatorname{N} = \phi \operatorname{kg} \operatorname{m}/\operatorname{s}^2 = G \frac{\mu_1 \mu_2}{\rho^2}\frac{\operatorname{kg}^2}{\operatorname{m}^2} $$
where $\phi$, $\mu_1$, $\mu_2$ and $\rho$ are pure numbers (they're the numerical values of the various quantities in SI units). So we need to get the dimensions of this to make sense, and just doing this it's immediately apparent that
$$G = \gamma \frac{\operatorname{m}^3}{\operatorname{kg} \operatorname{s}^2} $$
where $\gamma$ is a pure number, and is the numerical value of $G$ in SI units.
Alternatively if we put newtons back on the LHS we get
$$G = \gamma \frac{\operatorname{N} \operatorname{m}^2}{\operatorname{kg^2}} $$