The axioms of Peano arithmetic do not mention multiplication, but multiplication can be constructed in it from facts about addition, given complete induction. Unfortunately Peano's axiom of induction is not fully reducible to a collection of first-order statements.
The issue is not about multiplication per se, or even about the combination of addition and multiplication. The theory of Real Closed Fields has both, and is consistent and complete. The issue is about the strength of induction.
The induction axioms in Presburger arithmetic are the first order approximation of the Peano axiom, and basically do not allow for establishing facts about other facts that have, themselves, to be established inductively.
You cannot get real recursion off the ground unless you have a second order theory of counting, that allows you to represent the sets of integers for with the results are already established.
So to get a first order theory to start doing Gödel's proof, you have to bring in either infinitely many facts about addition, which are needed to establish the relevant results about multiplication, or a few facts about multiplication, itself, as additional axioms.