Maybe that is 'simple' when solving the problem nature had, it's just that we're not used to this kind of problems.
Feel free to correct me further.
The complexity of a geometrical structure (like a cube, or a protein) is one thing. The complexity of a process that fulfills a function (engine of a car) is another thing. One is static, the other is dynamic. One just sits there. Like a pile of rocks. The other one takes an input and process it into an output, in a specified, repeatable manner.
A pile of rocks, in a particular context, solves the problem of surviving the surrounding conditions. Is it the simplest solution? Who cares!
DNA replication on the other hand? What did Mother Nature drink to come up with this problem and try to solve it?
Funny about the rock thing, I never know what to make about them, I would need to add an 'adaptability' rule to my core ones.
DNA replication did not emerge from the early organisms. Before replication, we could investigate about DNA or prototypical forms of DNA as forms of variable input transformation. This kind of meta-encoding (sorry programmer POV leaking) of input tranformation is probably not the first minimum but pressure + time pushed the versatility needs up (again programmer POV).
I'd add to that: there is even a chance (quite high btw) we are not yet seeing all the problems nature solves AND maybe we never will even though we are constantly and exponentially growing our understanding... always, forever, now.