How did words like align get a g?

One answer for Is there an etymological explanation for the silent ‘g’ in “paradigm”? mentions that words such as align, apophthegm, arraign, assign, benign, campaign, consign, deign, design, diaphragm, ensign, feign, foreign, hypodigm, malign, phlegm, reign, resign, sign, sovereign, syntagm all have a silent "g" due to the final nasal.

All of the words ending in "-gn" (I'm not concerned with "-gm") ultimately come from Latin, and most have consistently had a "g" since Latin:

• assign: from Old French assigner, from Latin assignō
• benign: from Old French benigne, from Latin benignus
• consign: from Old French consigner or directly from Latin cōnsignō
• deign: from Middle English deignen, from Old French deignier, from Latin dīgnō, dīgnārī, from dīgnus
• design: from Old French designer, from Latin designō
• ensign: from Old French enseigne, from Latin īnsignia
• malign: from Old French maligne, from Latin malignus
• reign: from Middle English regnen, borrowed from Old French regner, from Latin rēgnō
• resign: from Anglo-Norman resigner, Middle French resigner, from Latin resignāre
• sign: from Middle English signe, sygne, syng, seine, sine, syne, from Old English seġn and Old French signe, seing; both from Latin signum

The "g" in the following words can be easily explained:

• campaign: from French campagne, from Italian campagna, from Late Latin campānia, from Latin campus
• foreign: from Middle English forein, from Old French forain, from Vulgar Latin *forānus, from Latin forās. The spelling altered perhaps by analogy with sovereign.
• sovereign: from Old French soverain, from Vulgar Latin *superānus, from Latin super. Spelling influenced by folk-etymology association with reign

However, the following words get a "g" for no clear reason:

• align: from Middle English alynen, alinen, from Middle French aligner, from Old French alignier, from Latin lineare
• arraign: from Old French araisnier, from a- +‎ raison +‎ -ier or from Vulgar Latin *adratiōnāre
• feign: from Middle English feynen, feinen, from Old French feindre, from Latin fingere

Note that Latin fingere is spelt with "ng", not "gn", which then changes to "nd" in Old French before changing to "n" in Middle English and finally "gn" in modern English. I couldn't find the missing etymology.

It looks like perhaps a Middle English spelling with "yn" is a predictor of "gn" in modern English which is why I highlighted all of signe, sygne, and syne as well, but that could be a red herring. How did this final set of words end up with a "g" in them?

In Latin, "gn" was pronounced as two consonants

In Latin, the spelling <gn> represented a sequence of consonants or a heterosyllabic consonant cluster. While we don't know the exact pronunciation for sure, current scholarship leans in favor of the value [ŋn], a velar nasal followed by a coronal nasal. The history of the similar pronunciation [gn] (a voiced velar plosive followed by a coronal nasal) is a bit unclear, but it certainly was used in later time periods when Latin was no longer spoken as a native language. Even if it was pronounced as [ŋn], many modern phonemic analyses of Latin treat <gn> as /gn/, with an allophonic realization of /g/ as [ŋ] in this environment. Interestingly, the situation with <gm> doesn't seem to have been exactly parallel, as there isn't really any evidence for a pronunciation *[ŋm] existing in Latin. It may be relevant that Classical Latin "gm" mostly arose from relatively late processes of vowel syncope (e.g. tegmen < tegimen): ancient "gm" clusters seem to have changed in Latin to [mm], with assimilation in both manner and place of the first consonant to the second (e.g. in the word flamma "flame").

I wrote a more detailed post about the pronunciation of "gn" in Latin on the Latin SE site; my main source was W. Sidney Allen's Vox Latina.

In many Romance languages, Latin "gn" turned into a palatal nasal (a single consonant)

As far as I know, none of the Romance languages retains either [ŋn] or [gn] in inherited/popular vocabulary. (The sequence /gn/ does show up in a number of languages in some learned vocabulary from Latin or Greek; e.g. French ignition.) In Romanian, Latin "gn" became "mn" [mn] (a similar sound change affected Latin "ct", changing it to Romanian "pt" [pt]). In Western and Italian Romance languages, Latin "gn" has generally become a palatal nasal [ɲ] (in standard Italian, the palatal nasal is an "intrinsic geminate", meaning it is always pronounced as a long consonant [ɲː] when it occurs between vowels).

Some of the sources that I've read, such as Allen, say that [ɲ] points towards earlier [gn], via sound changes like [gn] > [ɣn] > [jn] > [ɲ(ː)], but honestly I'm not sure why we couldn't have gotten [ɲ] from [ŋn] via some process like [ŋn] > [ɲn] > [ɲ(ː)]. Anyway, I don't think the details of the sound changes leading up to [ɲ] are particularly relevant to your question. The important point is that Western and Italian Romance languages developed an alternative pronunciation for "gn" that was not the same as the pronunciation that had been used in Latin. Despite the change in pronunciation from Latin, the spelling <gn> was used for this new sound in various Romance languages (although as tchrist's comment mentions, not all: <nh> was also used in some languages, as it still is in modern Portuguese; modern Spanish uses <ñ>; and at one point in French the trigraph <ign> was used to represent [ɲ], a convention that has left a remnant in the modern French spelling <oignon>—see the French SE posts L'orthographe « ognon » a-t-elle une date de péremption ? and Oignon/ognon : découpage syllabique ? for more details).

Palatal nasals from sources other than Latin "gn" are nevertheless "unetymologically" (but regularly) written with "gn" in certain Romance languages (e.g. French, Italian)

The [ɲ] sound in Romance languages has other sources than Latin "gn". In your question, you've mentioned some words that exemplify this: French campagne and Italian campagna come from a Latin word ending in "nia". In words like this, [ɲ] developed from coalescence of /n/ with a following palatal glide, but the digraph <gn> is nevertheless used in Italian and French. This could be considered "unetymological", but it's not irregular: <gn> has become the regular way of representing the palatal nasal, regardless of etymology, in these two languages. Furthermore, Italian uses <gl> and <gli> to represent the palatal lateral, which is often not derived from Latin "gl": e.g. Italian foglio [ˈfɔʎːo] "sheet" comes from Latin folium.

The same development explains the <gn> in French ligne "line" from Latin linea (the "e" in the Latin form turned into a palatal glide, which then coalesced with the preceding nasal to form [ɲ]). The English word align is related to French ligne.

Another historical French sound change got rid of [ɲ] when it came before another consonant, replacing it with [n] (along with a palatal offglide on the preceding vowel). This is why the infinitive form feindre has "n" instead of "gn". The "d" here arose by epenthesis of -nr- to -ndr-. But the present participle stem feign- was not affected by either of these sound changes, because the sound [ɲ] here came before a vowel. The development of Latin /ng/ to French [ɲ] in certain contexts is a regular sound change, and the corresponding spelling change to <gn> is also expected, not irregular. I wrote an answer to a related question on Linguistics SE: How did OF. peindre derive from L. pingere, with a “-ng-” > “-nd-” change?

"arraign": unlike the other words mentioned, it doesn't seem to have come from a Romance word with a palatal nasal

The word arraign is the only example you gave where it seems impossible to explain the use of <gn> in terms of influence from the spelling of the French etymon. The OED says it comes from "Anglo-Norman arainer, areiner, arener, Old French arais-, areis-, aresnier < Latin adratiōnāre". Although some French words now spelled with <ni> seem to have had old variants with <gn> (e.g. the OED says <magnioc> existed as a 17th-century French form of manioc), I haven't found any evidence that this is the case for araisnier. So the use of <gn> in the spelling of this word does seem to have originated in English, by analogy with the spelling of other words.

As your question mentions, two other words that seem to be spelled with <gn> in Modern English for similar reasons are sovereign and foreign.

I don't think the use of "y" in Middle English spelling is very relevant to the use of "gn" in Modern English spelling

In Middle English, Y was used in many of the same ways as I. Apparently, Y was particularly likely to replace I when the vowel was "long", or when the letter was next to one of the "minim" letters M or N (sequences like im, in, mi, ni are supposed to have been avoided in English writing at certain time periods because of the similarity of the strokes used to write these letters). (Complete Works Of Geoffrey Chaucer, W.W. Skeat) So I think feynen and feinen or alynen and alinen are basically equivalent spellings.

From Etymology online:

• align: early 15c. The French spelling with -g- is unetymological, and aline was an early form in English.
• arraign: The unetymological -g- is a 16c. overcorrection based on reign, etc.
• feign: A 17c. respelling. This word acquired a -g- in imitation of the French present participle stem feign- and the Latin verb.