Here is a method that uses less resources than does the first answer.
Let [x4..x0] and [y4..y0] be the inputs, [z4..z0] =([x4..x0]+[y4..y0])%26 the desired output. For simplicity, I assimilate the bit vector [x4..x0] and the integer it represents, in binary, MSbit first.
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 thus have [z4..z1] = ([v4..v0]+[w1..w0])%16 !!
Build [z4..z1] = ([v4..v0]+[w1..w0])%16 (with one 4-bit adder, disregarding carry out).
Total: two 4-bit adders with carry input and output, e.g. the 74HC83 pictured below (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 three other common 14-pin ICs, leaving 6 unused 2-input gates.
74HC83 (4-Bit Binary Full Adder with Fast Carry) logic diagram