There are some regional differences in contemporary Ecclesiastical Latin, mostly in pronunciation (for example, "c" before e/i can be pronounced as [ʧ] or [ts]). Also, I know that as non-natives, medieval Latin speakers sometimes introduced words from their native languages. On the other hand, various dialects were at least somewhat mutually understandable. My layman guess is that they differed about as much as various dialects of contemporary English, or little more.
For example, let's pick 13th century and Latin dialects spoken in Italy, British Isles, Sweden and Bohemia - if people from these regions met, how difficult would it be for them to understand each other, and what would be the main differences?
No need to describe these particular dialects in detail though, it's just an example.
EDIT: Let's take modern ecclesiastical Latin as a reference. Speakers of some of the different dialects may need some time to accommodate to even understand each other, and the differences may be funny. Do we have any evidence that high medieval Latin dialects were more, less or about as different as those in ecclesiastical Latin today?
An example of various dialects together is here (mostly in ecclesiastical Latin, with French introduction). The differences are probably slightly exaggerated to enhance the fun effect, but only dialects of Western Europe and America are included, other dialects like Polish one have other peculiarities.