I don't think Italian has a perfect equivalent of the word overkill. You can use different terms in different situations.
Translating it as eccessivamente complicato isn't optimal because overkill implies the existence of a much simpler alternative, while this translation does not give this suggestion.
Translating it with esagerato comes probably closer to the inteded meaning, although it's not clear that the exaggeration is in the (avoidable) complexity of the solution. Depending on the context it may be a perfect match or not.
However there is an idiomatic sentence that provides exactly that meaning:
Questa soluzione è come sparare ad una mosca con un cannone.
Literally:
This solution is like shooting a fly with a cannon.
Which, according to this thread in the word-reference forum, would be well suited to be translated as overkill.
I believe it conveys the correct meaning: the solution is too complicated for the given task. You are doing something that can be avoided, reducing complexities and obtaining the same results.