Right, if only there were a logic block to select one input from many? Some sort of "plexer", with "multi" inputs? :)
(Not trying to be snide, just... it's called a multiplexer, it's rather hard to name without giving it away, okay?..)
But then, what drives the selection? Okay so we're going to need a state machine. Not much of one, probably just a couple counters and latches to sequence everything. Right so you add the low bits, you get your 5 bits out (4 + carry), loop the one bit (carry) back in with the next nibble, and so on down the line, sourcing from input register N and latching into output register N, taking carry from N-1 (the first carry being provided from a separate carry input pin, most likely), and when the last register is strobed out, deassert all the internal enables/strobes, clear the counter(s) and set a flag "result ready", something like that maybe, so the surrounding system knows when to check for output.
Also, is this a "full" 4-bit adder i.e. with carry input, or do we actually need to chop it down by one i.e. do it 3 bits + carry at a time? Either way, same structure, just different bit assignments, and number of iterations.
Or you could do it with shift registers, since the input and output registers don't have to be addressable in any order, they're only ever used in strict sequence. In that case, four parallel-load serial-shift registers (32 bits long, each) could be used for the input, and serial-in, parallel-out for the output. Basically a bit-serial architecture but with a couple bits working in parallel. Or put another way: it's still digit-serial but it's in base 16 instead of base 2.
And then to make it a full proper block, we need some kind of access specification. Maybe we have a 4-bit bus assigning 32 individually addressable registers, or 8-bit x 16, etc.; this would be fine for a memory-mapped peripheral (many MCUs implement arithmetic extensions in this sort of way). Maybe it's streaming (bit- or word-serial) and the design has to be a bit more finely crafted to that (a transaction being packet-oriented or something; data is always in motion, no local memory needed (beyond the carry that is)). And probably some control signals, like bus strobe (read/write?), start cycle, stop cycle/reset, cycle complete, and clock.