Let [x4..x0] and [y4..y0] be the inputs, [z4..z0] =([x4..x0]+[y4..y0])%26 the desired output.
Build z0 = x0^y0.
Build u0 = x0&y0. We have [z4..z1] = ([x4..x1]+[y4..y1]+u0)%13.
Build [v4..v0] = [x4..x1]+[y4..y1]+u0 (that can be done with one 4-bit adder with carry input and output). We have [v4..v0]<26, and [z4..z1] = [v4..v0]%13.
Build w0 = v4|(v3&v2&(v1|v0)). It is 0 iff [v4..v0]<13, 1 otherwise. Let w1 = w0 (no cost), now [w1..w0] is 0 iff [v4..v0]<13, 3 otherwise. We have [z4..z1] = ([v4..v0]+[w1..w0])%16.
Build [z4..z1] = ([v4..v0]+[w1..w0])%16 (that can be done with less than one 4-bit adder).
Total: two 4-bit adders with carry input and output (for the second, carry input and the two high-order bits of one input are grounded, carry output is unconnected); 3 AND, 2 OR, 1 XOR. That's five common 14-pin ICs, leaving 6 unused 2-input gates. I think that beats the first answer