Freedom is a transcendental condition for the Categorical Imperative to be real. And the four different formulations mean exactly the same for him.
I will argue how for Kant, the possibility of the experience of a categorical imperative presupposes freedom as necessary in his mature ethical system. Before that, the systematic relation between freedom and the CI changed as I want to illustrate by slides I made for a presentation recently to illustrate the transition (they are simplifying things, although it might not look like it).
The question why the formulations are identical and in which sense is - obviously - answered within the Groundwork. Note that autonomy and being an end in itself is not freedom in a liberal sense. It essentially is being able to subdue oneself under the CI and through this being able to give universal laws (that are truly universal).
There is no inner conflict between the right of freedom and the Formula of universal law, as you may see directly from the following quote:
The latter principle [=the CI] must undoubtedly take precedence; for, as a principle of right, it has unconditional necessity. (Towards Perpetual Peace, 8:377)
Also, it is in the very quote Hodgson provides:
from being constrained by another’s choice), insofar as it can
coexist with the freedom of every other in accordance with a universal
law, is the only original right belonging to every human being by virtue
of his humanity. (Doctrine of Right, 6:237)
I will nevertheless provide an answer that tries to fully answer both the title question as well as digressions within the question.
All quotes from the Cambridge Editions of the works.
Critique of Pure Reason
In his first Critique, he raises the point that imperatives as such transcend the realm of nature and its standing under the Law of Causality, because they express something that is not existent in nature and therefore laws of freedom:
Hence this [i.e. considering what is good per reason] also yields laws that are imperatives, i.e., objective laws of freedom, and that say what ought to happen, even though perhaps it never does happen, and that are thereby distinguished from laws of nature, which deal only with that which does happen, on which account the former are also called practical laws. (A802|B830, emphasis mine)
This is why
Practical freedom can be proved through experience. (ibid)
because we obviously do know imperatives and occasionally act according to them. Nevertheless, transcendental freedom (and its reality!), i.e. "a faculty of absolutely beginning a state, and hence also a series of its consequences"(A445|B473) remains a problem:
We thus cognize practical freedom
through experience, as one of the natural causes, namely a causality of
reason in the determination of the will, whereas transcendental freedom requires an independence of this reason itself (with regard to its
causality for initiating a series of appearances) from all determining
causes of the world of the senses, and to this extent seems to be contrary to the law of nature, thus to all possible experience, and so remains a problem. (A803|B831, emphasis mine)
He does something pretty messy to justify the reality of freedom afterwards, using God both as a starting point as well as His reality as conclusion and therefore not tackling the possibility of all of this being mere illusion, as illustrated in the slide:
Groundwork for Metaphysics of Morals
Here, Kant learned out of the mistakes of CPR and sees it as his first and foremost task to justify the reality of freedom (which he tries in Chapter three!).
In the first two Parts and the first two subheadings of the third part he still does only argue why and how things relate to each other, ending with the statement that (the idea of) freedom, i.e. transcendental freedom, may be a necessary condition for free will and morality and that the Categorical Imperative is an expression of a free will ("a free will and a will under moral laws are one and the same", 4:447). But we in no way proved that we have free will, i.e. that the CI is binding for us:
We last traced the determinate concept of morality back to the idea
of freedom; which we could not, however, prove as something actual
even in ourselves or in human nature; we saw only that we must presuppose it if we want to think of a being as rational and endowed [...] with a will; and thus we find that on just the same grounds we must ascribe this property of determining itself to action under the idea of its freedom to every being endowed with reason and will. [...] But why, then, ought I to subject myself to this principle, and do so as a rational being as such, and hence thereby
also all other beings endowed with reason? (4:449, emphasis mine)
I think this partly answers the question regarding the difference. If we see freedom as necessary for rational beings, we have to presuppose it for every rational being, at least in principle. If we do this, there is free will. If there is free will, there is autonomy. If there is autonomy, there is CI (see also 4:447). This is how he comes to the Kingdom of Ends Formula: If every single rational being is autonomous and in fact giving universal laws through its free will, they are systematically connected to each other through these laws:
The above three ways of representing the principle of morality are
fundamentally only so many formulae of the same law, one of
which of itself unites the other two within it. However, there is yet a
dissimilarity among them, which is indeed subjectively rather than objectively practical, namely to bring an idea of reason closer to intuition
(according to a certain analogy) and thereby to feeling. For all maxims
l) a form, which consists in universality, and then the formula of the
moral imperative is expressed as follows: that maxims must be chosen as
if they were to hold as universal laws of nature;
2) a matter, namely an end, and then the formula says: that a rational
being, as an end according to its nature, and hence as an end in itself,
must serve for every maxim as the limiting condition of all merely relative and arbitrary ends;
3) a complete determination of all maxims by the that formula, name-
ly: that all maxims from one's own legislation ought to harmonize
into a possible kingdom of ends as a kingdom of nature. (4:436)
The unifying formula is the Formula of Universal Law:
But in moral judging it is better always to proceed by the strict method,
and make the foundation the universal formula of the categorical imperative: act according to the maxim that can make itself at the same time a universal law. (ibid)
The question why the CI is binding is not to be answered here, but I think it has become clear that if we have a CI that is real, freedom will be real as well, since it has to be presupposed. But he thinks he does deduce (i.e. in the legal sense of justify) the reality of the CI later.
All this can be illustrated as follows:
Critique of Practical Reason
This is the most mature moral system of Kant, where he again rearranges his concepts and includes the other transcendental ideas, namely the immortal soul and God, into the system. It may suffice to say that he undertakes a bit of a shortcut here, stating that the CI is a 'fact of reason', i.e. also a fact of experience and therefore real (regarding this relationship see Critique of Pure Reason, A 156|B 195), and so freedom is real as well (5:32).
Another remarkable difference is that he rejects that the Universal Formula is directly applicable, but needs forms accesable through intuition, i.e. exactly one of the forms mentioned above (he explicitely uses the Formula of Law of Nature).
For the sake of completeness, my slide illustrating this system: