Has decidability got something to do with primes?

Goedel did indeed use the Chinese remainder theorem in his proof of the Incompleteness theorem. This was used in what you describe as the `boring' part of the proof, the arithmetization of syntax. Contemporary researchers often agree with your later assessment, however, that the arithmetization of syntax is profound. This is the part of the proof that reveals the self-referential nature of elementary number theory, for example, since in talking about numbers we can in effect talk about statements involving numbers. Ultimately, we arrive in this way at a sentence that asserts its own unprovability, and this gives the Incompleteness Theorem straight away.

But there are other coding methods besides the Chinese Remainder theorem, and not all of them involve primes directly. For example, the only reason Goedel needed CRT was that he worked in a very limited formal language, just the ring theory language. But one can just as easily work in a richer language, with all primitive recursive functions, and the proof proceeds mostly as before, with a somewhat easier time for the coding part, involving no primes. Other proofs formalize the theory in the hereditary finite sets HF, which is mutually interpreted with the natural numbers N, and then the coding is fundamentally set-theoretic, also involving no primes numbers especially.

In response to your statement: "It appears that the condition that primes are definable in the theory will implies incompleteness."

The primes being definable in an arithmetic theory does not necessarily lead to incompleteness. The theory of Skolem arithmetic ($Th(\langle\mathbb{N},*\rangle)$) is decidable and admits quantifier elimination (it is the elementary true theory of the weak-direct power of the standard model of Presburger arithmetic, so Feferman-Vaught quantifier-elimination lifting applies). A predicate for primality can easily be expressed in the language of this theory. This is due to Skolem and Mostowski initially, and to Feferman-Vaught when obtained in terms of weak-direct powers.

Moreover, Skolem arithmetic extended with the usual order restricted to primes is decidable, admits quantifier elimination, and in fact $Th(\langle\mathbb{N},*,<_p\rangle)$ and $Th(\langle\omega^\omega,+\rangle)$ are reducible to each other in linear time. This is due to Francoise Maurin (see "The Theory of Integer Multiplication with Order Restricted to Primes in Decidable" - J. Symbolic Logic, Volume 62, Issue 1 (1997), 123-130).

Note that in this latter case, the ordering cannot be the full ordering on the natural numbers, as this would allow one to define a successor predicate, and Julia Robinson showed successor and multiplication are sufficient for defining addition.

The role of primes in Gödel's Incompleteness Theorem can be better understood by looking at Robinson's Q, which is one of the weakest theories of arithmetic for which Gödel's Incompleteness Theorem holds. Robinson derived his original axioms for Q by looking at the axioms of PA that were used in the proof that every computable function can be represented in PA, which is the key part of Gödel's argument.

A simple theory that interprets Robinson's Q is the theory of discrete ordered rings with induction for open formulas, i.e. the schema φ(0) ∧ ∀x(φ(x) → φ(x+1)) → ∀x(x ≥ 0 → φ(x)), where φ is a quantifier-free formula in the language of ordered rings which may contain free variables other than x. (The only existential quantifier in the axiomatization of Q, namely in the axiom x = 0 ∨ ∃y(x = Sy), can be eliminated since we now have subtraction.)

The theory of discrete ordered rings with open induction has interested many logicians. The first to study this theory was Shepherdson (A non-standard model for a free variable fragment of number theory, MR161798) who showed that this theory cannot prove that √2 is irrational. It follows that Robinson's Q also cannot prove the irrationality of √2. Since the irrationality of √2 is a consequence of unique factorization into primes, Robinson's Q cannot prove that either.

Shepherdson's model where √2 is rational is the ring S whose elements are expressions of the form $$a_0 + a_1T^{q_1} + \cdots + a_kT^{q_k}$$ where T is an indeterminate, the exponents 0 < q₁ < ... < q_k are positive rationals, the coefficient a₀ is an integer, and the remaining coefficients a₁,...,a_k are real algebraic numbers. Positivity is determined by the sign of the leading coefficient a_k; this corresponds to making T infinitely large. The fact that this satisfies open induction is very remarkable. In this ring S, the only primes are the primes from ℤ, so there are simply no infinite primes. Therefore, Robinson's Q cannot prove that the primes are unbounded.

Still stranger discrete ordered rings with open induction have been constructed by Macintyre and Marker (Primes and their residue rings in models of open induction, MR1001418). For example, they construct such a ring where there are unboundedly many primes, but all infinite primes are congruent to 1 modulo 4.

It is apparently still unknown whether the induction axiom for bounded quantifier formulas (IΔ₀) proves the unboundedness of prime numbers. This problem was raised by Wilkie and the first partial answer came from Alan Woods who linked it to a pigeonhole principle, together Paris, Wilkie, and Woods (Provability of the pigeonhole principle and the existence of infinitely many primes, MR973114) showed that the unboundedness of prime numbers is provable in a very small extension of IΔ₀. (See also this recent article by Woods and Cornaros MR2518806.)

The above shows that a sound theory of primes and factorization is not necessary for Gödel's Incompleteness Theorem. However, this should be taken with a grain of salt. The key feature of Robinson's Q is that it correctly interprets the basic arithmetic as far as the standard natural numbers are concerned, and nothing more. The fact that Robinson's Q doesn't say much about what is happening outside the standard integers does not mean that the certain features, like primality, that make up the rich and complex structure of the standard integers is completely irrelevant to Gödel's Incompleteness Theorem.