How did people speaking different languages commun

There were interpreters, of course. But one way was using Latin as lingua franca, as this language was known by all educated people (then not too many) - including all the clergy, who were the admnistrative backbone.

Modern romances are still mutually intellegible for the most part. Rumanian and Sardinian may be the less simmilar to anything, followed by French. But many of the modern dialects didn't have the importance that they have now. For instance Occitan, as spoken in Tolouse (not very diferent from Catalan) was a lingua franca of most Romanic countries, being the favorite tongue of trouvateurs but being very extended even south of the Pyrenees.

I don't know so much about Germanic languages but I'm prety sure that Lower German and Danish are not that different. But they probably had a dialect (let's say Frisian) that was lingua franca in most cases.