Let's look at each of these one-by-one:
いらっしゃる is a lexicalized contraction of 入{い}らせらる, which is described in 精選日国† as follows:
（動詞「いる(入)」の未然形に、尊敬の助動詞「す」の未然形、同じく「られる（らる）」の付いたもの）「入る」の尊敬語。おはいりになる。
In other words, it was a combination of 入る with the respect auxiliary す and the passive auxiliary らる (in modern Japanese られる).
くださる is a lexicalized combination of 下す with る (modern Japanese れる) added, reanalyzed as a 四段動詞 → 五段動詞. From 精選日国:
くださ-・る【下】
①〔他ラ下二〕⇒くだされる（下―）
②〔他ラ五(四)〕（近世以降、①が四段活用化したもの） [...]
くださ-・れる【下―】
〔他ラ下一〕(文)くださ・る〔他ラ下二〕〔他ラ下二〕(動詞「くだす(下)」に、受身、尊敬の助動詞「る」のついてできたもの) [...]
なさる is likewise lexicalized from 為す with る added (modern Japanese れる), reanalyzed as a 四段動詞 → 五段動詞. From 精選日国:
なさ-る【為】
①〔他ラ下二〕⇒なされる（為）
②〔他ラ五(四)〕①（が四段活用化したもの） [...]
なさ-・れる
〔他ラ下一〕(文)なさ・る〔他ラ下二〕(動詞「なす(為)」に尊敬の助動詞「れる(る)」の付いてできたもの) [...]
おっしゃる is given multiple theories in 精選日国:
室町時代に現れた「おしゃる」が江戸時代に「おっしゃる」となったとする説がある一方、二つとも同時的に例があるため共に「おおせある」または、「おおせらる」からの変化形と見る説もある。
Other dictionaries such as 広辞苑 and 大辞林 say it's derived from おおせある without presenting any alternative theories. Either おおせある and おおせらる would then come from 仰す (おほす), which according to 旺文社国語辞典 is derived from the causative form of 負ふ (おふ), used to mean 「言葉を負わせる」. After this, either らる or ある was added.
So of these four, three clearly have the passive/honorific auxiliary (ら)る, which is in modern Japanese (ら)れる. The fourth may have it, or it may have ある instead; if we compare a fifth verb, ござる, we definitely have ある:
ござる is unusual in beginning with a voiced obstruent. In this case this is because the word is not entirely native, but a fusion of the Sino-Japanese 御座(ご-ざ) and ある. From 精選日国:
ござ・る(御座)
〔自ラ四〕（「ござある」の変化した語）
This verb is often considered separately because only the lexicalized form with ます remains in the modern language, outside of jocular or anachronistic uses. From a historical perspective, though, it makes sense to consider it as part of the same subclass of verbs.
So we find that all five verbs have either （ら)れる -(r)are- or ある ar-. Martin notes that the passive doesn't attach to any of these verbs in A Reference Grammar of Japanese (1975), p.290:
We can find no causatives or passives for the subject-exalting verbs kudasáru, nasáru, ossyáru, or even irassyáru… We might ascribe the absence of such forms to the fact that it is usual to make the causative or passive BEFORE putting the sentence into any other conversion (though there are exceptions, as we will see below); but probably the real reason we lack the forms is that these verbs etymologically contain an occurrence of the passive as reflected in the -ar- with which each base end.
So Martin, at least, considers -(r)are- to contain ar-, though he doesn't explain specifically how he derives one from the other. But they're similar in form and function, so it makes sense to try to -(r)are- and ar- somehow. He notes a possible relationship on page 290 in a parenthetical:
(Chamberlain 199 derives -rare- from ár-i + é-ru.)
It's not clear to me which Chamberlain he's citing, but in any case it's very old, around a century ago. If we check a much newer reference, Frellesvig's A History of the Japanese Language (2010), we find on p.238:
The [Early Middle Japanese] causatives and passives seem to reflect a further morphologization of the derivational suffixes -(a)s- 'transitive' and -(a)r- 'intransitive'.
In any case, it does seem plausible to say that all of them contain ar- etymologically.
† 精選日国 is short for the full name of the dictionary, 「精選版 日本国語大辞典」.
