Let's look at each of these one-by-one:
いらっしゃる is a contraction of 入らせらる, which is the 文語 form of 入らせられる, a lexicalized combination of (入る→入ら) + (す→せ) + られる.
おっしゃる is a contraction of おおせある, which appears to be the simple combination of 仰す→仰せ and 有る (not 在る).
くださる appears to come from (下す→下さ) + る.
I'm not sure about なさる, but it seems likely that 為{な}さる is related to 為{な}す. It looks like (為す→為さ) + る, but since I'm making a guess, I'm probably wrong :-)
If my guess about なさる is right, then なさる and くださる share the morpheme る, which I suppose functions to make both of them honorific. The morpheme られる in いらっしゃる is not the same, but in this case probably has a similar function to る; the linked definitions for both る and られる say they can express 尊敬. The 有る in 仰せ有る also has an honorific sense--see 〔2〕-【5】 in 大辞林. In that sense, it says 有る attaches to the 連用形 of a verb, and 仰せ is exactly that, so it fits.
So I guess in all four, a suffix adds 尊敬 to the word, but the suffix in question isn't ある in each word. Rather, it's られる, ある, る, and maybe る if my guess is right.