The term 'religious freedom' in our current society implies a society that grants its citizens the right to follow any religion of their choosing or none at all, with formal, legal protections associated with this right.
Obviously this concept is fundamentally alien to a medieval European society. Religious tolerance is a much better term, but you have to remember that most medieval European societies were both ethnically and culturally homogenous. Uniformity of religious belief and worship were heavily reinforced by the weight of monolithic national cultures up until the arrival of the Reformation, but that came after the Medieval era and occurred during the early Renaissance.
During the Middle Ages, exposure to other beliefs and ways of doing things was extremely limited outside of major international trading centers for most Europeans. The comparatively cosmopolitan Muslim and Eastern Orthodox societies around the edges of the Mediterranean (including pre-Reconquista Spain and the Byzantine Empire) were very different in character and should not be used as examples to assert that religious diversity was normal. In the vast majority of medieval Europe, it was not.
