Secret Message Part 1, Elements
JavaScript (ES6), 881 871 bytes

Takes the input string in all caps.

s=&gt;(o={},'HEelLIithBEeryllMGagnesCAalcTIitanVanadCRhromGAallGEermanSEelenRBubidSRtrontYttrZRirconTCechnetRUuthenRHhodPDalladCDadmTEellurBAarCEerPRraseodymNDeodymPMromethSMamarEUuropGDadolinTBerbDYysprosERrbTMhulLUutetREhenIRridTLhallFRrancRAadACctinTHhorPArotactinUranAMmericCMurESinsteinFMermMDendelevLRawrencRFutherfordDBubnSGeaborgMTeitnerDSarmstadtRGoentgenFLlerovMCoscovLVivermorHydrogenBoronCarbonNitrogenOxygenFluorineNEeonALluminumPhosphorusSulfurCLhlorineARrgonMNanganeseZNincASrsenicBRromineKRryptonMOolybdenumIodineXEenonLAanthanumTAantalumPTlatinumATstatineRNadonTSennessineOGganessonNAsodiumKpotassiumFEironAGsilverWtungstenAUgoldHGmercury'.split(/([A-Z]+|[a-z]+)/).map((r,i,a)=&gt;i%4-3?0:o[e=a[i-2]]=i&gt;339?r[0].toUpperCase()+r.slice(1):e[0]+r+(i&lt;235?'ium':'')),g=([c,...s],r)=&gt;c?c&lt;'A'|c&gt;'Z'?g(s,r+c):o[c]&amp;&amp;g(s,r+o[c])||o[c+=s.shift()]&amp;&amp;g(s,r+o[c]):r)(s,'')||s


Extended test cases

Because this challenge is also a variant of the exact cover set problem, I've added the following test cases:


"NA" → "Sodium"
"NAG" → "N" + "AG" → "NitrogenSilver"
"NAP" → "NA" + "P" → "SodiumPhosphorus"




let f =

s=&gt;(o={},'HEelLIithBEeryllMGagnesCAalcTIitanVanadCRhromGAallGEermanSEelenRBubidSRtrontYttrZRirconTCechnetRUuthenRHhodPDalladCDadmTEellurBAarCEerPRraseodymNDeodymPMromethSMamarEUuropGDadolinTBerbDYysprosERrbTMhulLUutetREhenIRridTLhallFRrancRAadACctinTHhorPArotactinUranAMmericCMurESinsteinFMermMDendelevLRawrencRFutherfordDBubnSGeaborgMTeitnerDSarmstadtRGoentgenFLlerovMCoscovLVivermorHydrogenBoronCarbonNitrogenOxygenFluorineNEeonALluminumPhosphorusSulfurCLhlorineARrgonMNanganeseZNincASrsenicBRromineKRryptonMOolybdenumIodineXEenonLAanthanumTAantalumPTlatinumATstatineRNadonTSennessineOGganessonNAsodiumKpotassiumFEironAGsilverWtungstenAUgoldHGmercury'.split(/([A-Z]+|[a-z]+)/).map((r,i,a)=&gt;i%4-3?0:o[e=a[i-2]]=i&gt;339?r[0].toUpperCase()+r.slice(1):e[0]+r+(i&lt;235?'ium':'')),g=([c,...s],r)=&gt;c?c&lt;'A'|c&gt;'Z'?g(s,r+c):o[c]&amp;&amp;g(s,r+o[c])||o[c+=s.shift()]&amp;&amp;g(s,r+o[c]):r)(s,'')||s

console.log(f('HI!'))
console.log(f('THIS IS AN EXAMPLE'))
console.log(f('NEON'))
console.log(f('SNIP'))
console.log(f('NA'))
console.log(f('NAG'))
console.log(f('NAP'))




How?

Preliminary optimization

We ignore the following 26 elements entirely, because they can safely be replaced with two symbols of one character among BCFHIKNOPSUVWY:

Bh, Bi, Bk, Cf, Cn, Co, Cs, Cu, Hf, Ho, Hs, In, Nb,
Nh, Ni, No, Np, Os, Pb, Po, Pu, Sb, Sc, Si, Sn, Yb


Encoding and decoding the elements

We use an interlaced list of element symbols in upper case and element names in lower case. Symbols are always stored as-is, while names are shortened according to the following rules:


If the first letter of the name matches the first letter of the symbol, we omit it.
If the element passes rule #1 and its name ends in "ium", we omit this suffix.


Examples:


Ag / Silver: "AGsilver"
K / Potassium: "Kpotassium"
Zn / Zinc: "ZNinc"
He / Helium: "HEel"


The 58 elements that trigger both rules are stored at the beginning of the list, followed by the 27 elements that trigger rule #1 only, followed by the 7 elements that do not trigger any rule.

We decode this list to populate the lookup table o, where the keys are the symbols and the values are the decoded element names:

"HEelLIith[...]HGmercury"       // encoded list
.split(/([A-Z]+|[a-z]+)/)       // split it by character case, which gives:
                                // [ '', 'HE', '', 'el', '', 'LI', '', 'ith', etc. ]
.map((r, i, a) =&gt;               // for each item 'r' at position 'i' in this array 'a':
  i % 4 - 3 ?                   //   if we're not currently pointing to an element name:
    0                           //     do nothing
  :                             //   else:
    o[e = a[i - 2]] =           //     save o[e], where e = element symbol
      i &gt; 339 ?                 //     if symbol/name first letters do not match:
        r[0].toUpperCase() +    //       we need to capitalize the first letter of the name
        r.slice(1)              //       and keep the rest unchanged
      :                         //     else:
        e[0] +                  //       we use the first letter of the symbol,
        r +                     //       followed by the name,
        (i &lt; 235 ? 'ium' : '')  //       followed by the 'ium' suffix when appropriate
)                               // end of map()


Covering the input string

We try to replace all upper-case letters in the input string with element symbols, using the recursive function g() which eventually returns a replacement string or undefined if no exact cover is found:

g = ([c,                                  // c = next character
         ...s],                           // s = array of remaining characters
                r) =&gt;                     // r = replacement string
  c ?                                     // if there's still at least one character:
    c &lt; 'A' | c &gt; 'Z' ?                   //   if it's not an upper-case letter:
      g(s, r + c)                         //     just append it to 'r'
    :                                     //   else:
      o[c] &amp;&amp; g(s, r + o[c]) ||           //     try to find a symbol matching 'c'
      o[c += s.shift()] &amp;&amp; g(s, r + o[c]) //     or a symbol matching 'c' + the next char.
  :                                       // else:
    r                                     //   success: return 'r'