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 interger 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 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, 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. I think that uses less resources than does the [first answer][1]


74HC83 (4-Bit Binary Full Adder with Fast Carry) logic diagram![74HC83 (4-Bit Binary Full Adder with Fast Carry) logic diagram][2]


  [1]: https://electronics.stackexchange.com/a/65313/22496
  [2]: https://i.sstatic.net/KhSgr.png