I should mention I am only an interested amateur, I have no qualifications in any field other than IT/software engineering.

Assuming they only speak their native languages of the areas in which they were born and assuming that the highlander was from somewhere west of Inverness, the Irishman was from somewhere in the north of Ireland, the Englishman from somewhere around London and the Welshman from some place far form the marches (what would have been called Pura Wallia), then only the Irishman and the Scotsman would have been able to communicate. I picked these areas because people on boarders live in contact with speakers of other languages and frequently have some knowledge of the other languages that surround them (I'm not sourcing this as I don't feel it's a very bold claim).

The lack of communication of any of the others is the easiest to deal with, so let's tackle that first. We know that all of the languages in question are from the Indo-European language family. For an explanation of the evidence we have for this I suggest The Horse, the Wheel, and Language by David Anthony of the University of Pennsylvania. But that was a long time ago. Now the Welshman, the Scotsman, and the Irishman speak languages with a much closer relationship. The Irishman and the Scotsman both speak languages descended from Middle Irish or Early Modern Irish depending on how you count. But the Welshman would have spoken a language that was only a cousin to theirs. Let's compare Middle English, Middle Welsh and Old Irish. Even though they are not quite contemporaneous we can see the differences quite clearly.

Middle English (Chaucer):

The lyf so short, the craft so long to lerne, Th'assay so hard, so sharp the conquerynge, The dredful joye alwey that slit so yerne: Al this mene I by Love, that my felynge Astonyeth with his wonderful werkynge So sore, iwis, that whan I on hym thynke Nat wot I wel wher that I flete or wynke.

Middle Welsh (Pwyll Pendefig Dyfed):

Pwyll Pendefig Dyfed a oedd yn arglwydd ar seith cantref Dyfed. A threiglweith ydd oedd yn Arberth, prif lys iddaw, a dyfod yn ei fryd ac yn ei feddwl fyned i hela. Sef cyfeir o'i gyfoeth a fynnei ei hela, Glynn Cuch.

Old Irish (Foras Feasa ar Éirinn):

Cibé duine 'san mbioth chuireas roimhe Seanchus nó Sinnseardhacht críche ar bioth do leanmhain nó do lorgaireacht, is eadh dhligheas cinneadh ar an slíghe is soiléire nochtas fírinne stáide na críche, agus dáil na foirne áitigheas í, do chur go soléir síos: agus do bhrígh gur ghabhas rém' ais Foras Feasa ar Éirinn d'fhaisnéis, do mheasas ar dtús cuid d'á leathtrom agus d'á heugcómlann d'eugnach; agus go háirithe an t-eugcomhthrom atá ag a dhéanamh ar a háitigtheoiribh, mar atáid na Sean-Ghaill atá 'na seilbh tuilleadh agus ceithre chéad bliadhan ó ghabháltas Gall i leith, mar aon re Gaedhealaibh atá 'na seilbh (beagnach), re trí mhíle bliadhan. Óir ní fhuil stáraidhe ó shoin i leith d'á scríobhann uirre nach ag iarraidh lochta agus toibhéime do thabhairt do Shean-Ghallaibh agus do Ghaedealaibh bhíd.

Written language is only a reflection of spoken language. So it's hard to say how similar the real spoken language of the Irishman and the Scotsman would have been but it would have been simply dialectal. And there is a reason that I chose the north of Ireland as it would have been the closest to what was spoken in the western part of the highlands. It should be noted that there were some Scandinavian speaking communities on the periphery of the area commonly considered the "highlands". We Americans don't realize the linguistic diversity that was present in Europe in the middle ages and it has survived to some extent into the modern period. Nevertheless, literary Gaelic (the Celtic language of Scotland) and literary Irish (the Celtic language of Irish) were the same language up to the 18th century (Stair na Gaeilge in ómós, The Celtic Languages). But that probably hides the linguistic variation that existed in the spoken language even this far back. If you take, as an example, the current written standard of Irish, An Caighdeán Oifigiúil, and learn it, you are going to have a less than easy time communicating with any native speaker of any of the dialects unless they are also familiar with the standard. But it's only a bit of trouble.

In the 16th century Irish was the language of nearly everyone in Ireland. The educated and upper classes, moreover, were familiar with a standardised literary dialect, Classical Irish, used throughout the Gaelic world. This dialect was the special care of poets, who used it most notably for intricate verse in praise of the Gaelic and Norman-Gaelic aristocracy, their patrons.

When, in the 17th century, that aristocracy was annihilated or dispersed and the Bardic schools suppressed, Classical Irish began to die out (though its spelling, with modifications, survived until the spelling reform of 1945). Popular dialects, which undoubtedly had always been present in Irish, as in any language, came to the fore.

...

Two hundred years ago a good speaker of Irish, travelling slowly from Kerry to Antrim (and on to the north of Scotland), could have spoken the language all the way and noticed only minute dialectal changes as he passed from place to place. One dialect shaded into another in the most gradual fashion.

-Mícheal Ó Siadhal, Learning Irish.

If that was the situation in the 18th century, the languages had to have been more similar in the 1300s. Looking at the text above from Chaucer, a native speaker of Modern English can pretty much understand it. I can't help but think that if I were sat next to Chaucer in a pub we would have a hard time talking at first but it would only take us a few hours before we could communicate pretty well. And that's with 600 years separating our languages. So we have to expect that the Scotsman and the Irishman would be able to talk given a bit of time to get used to each other's accent. Imagine taking my wife's 90 year-old grandmother from the hills of Kentucky and putting her in the same room as a woman of the same age from some place in rural England. That's how I imagine it would be. But the other speakers have no hope. They speak languages whose families are separated by thousands of years.

From a practical and non-scholarly perspective the modern similarities of these two languages was well illustrated in an episode of the Irish Language show Cladaigh Chonamara where the host, Donnacha Mac Con Iomaire, sails around the coast of Ireland up to Scotland and down to the Isle of Man. He stops and speaks to some speakers of Gaelic and it seems to take a little bit but they are able to make themselves understood. Mac Con Iomaire is actually surprised by this, or at least seems to be in the show, if my memory serves me. Unfortunately I cannot find this episode online. I thought I had, ehem, obtained a copy of it a while ago so I will look through my resources and see if I can determine which episode it was.

References

The Horse, the Wheel, and Language, David Anthony

Old English: A Linguistic Introduciton, Jeremy J. Smith

A Book of Middle ENglish, J.A. Burrow and Thorlac Turville-Petre

The Celtic languages Routledge

An Introduction to the Celtic Languages, Paul Russell

A Grammar of Old Irish, R. Thurneysen

Stair na Gaeilge in ómós, Pádraig Ó Fiannachta

Learning Irish, Mícheál Ó Siadhail

An Caighdeán Oifigiúil, 2017 - https://www.oireachtas.ie/en/publications/?q=An%20Caighde%C3%A1n%20Oifigi%C3%BAil

For an interesting treatment of attitudes that native speakers have and have had to the Standard see, Leabhar Mór Bhriathra na Gaeilge, A.J. Hughes (dual Irish and English text).

Old and Middle Welsh - http://people.ds.cam.ac.uk/dwew2/old_and_middle_welsh.pdf

​