Consider the sentence $\theta$: $$\exists m,n\, (2n=2m+1)$$ This is the negation of the first sentence in the above question. In relational form this is $$\exists m,n,u,v\, (Smmu \wedge Snnv \wedge Ruv)$$ where $Sabc$ is the relation for $a+b=c$ and $Ruv$ is the relation for $u+1=v$.
To find out whether $\theta$ is true arithmetically, we can incorporate clauses for the Peano definition of addition and the uniqueness of addition, and then ask whether there is an $\omega$-model for the sentence:
\begin{align} \forall a,b,c,d,e &(Sa0a\\ &\wedge\, (Rbc \wedge Rde \wedge Sabd \rightarrow Sace) \\ &\wedge\,(Sabc \wedge Sabd \rightarrow c=d))\\ \wedge\, \exists m,n,u,v\, &(Smmu \wedge Snnv \wedge Ruv) \end{align}
The key definition of an $\omega$-model is "an $\omega$-model for the language $(R_1, \ldots R_n)$ is a model $M$ such that $(|M|,R_1)$ is isomorphic to $(\omega, x +1=y)$". In this case we take $R_1$ to be the above $R$, and $R_2$ to be the above $S$, though this is not specified in the paper, and the whole definition is hidden inside the definition of a particular set, in the middle of theorem 7.10, at the top of page 415.
The advantage of using an $\omega$-model is that in an $\omega$-model the clauses above are enough to determine the addition relation completely, and to determine that any two elements can be added. Again, this is the only way I see to make sense of the argument, even though the paper does not specify this use of those clauses.
So the difference in the treatment of the two original sentences is that the procedure for the first only needs to incorporate the Peano definition of addition, and the procedure for the second needs to incorporate the Peano definitions of both addition and multiplication.
To continue with the procedure for $\theta$, we transform it further into prenex form for $G_1(\theta)$. (The paper also says to put the quantifier-free portion into $\bigvee_i \bigwedge_j$ form, but that does not seem necessary.) Then we can presumably apply the rest of the procedure to calculate $G_2(\theta)$, $G_3(\theta)$, and finally the desired $G(\theta)$ in the language of the monadic theory of order. I haven't done so yet.
I also see a few noteworthy items in the rest of the procedure:
- Step (1) seems to have a typo, where $l<0$ should read $l>0$.
- Steps (1), (3), (4) refer to $\psi$, which is defined on p. 413 using the definition of $\theta$ on p. 411.
- Step (3) seems to have a typo, where $\bigwedge_i \bigvee_j$ should read $\bigvee_i \bigwedge_j$ as in the definition of $G_1$.
- Step (4) seems to define $\chi^*$ as $\alpha \wedge \beta \wedge \gamma \wedge \delta \wedge \epsilon$, even though the clauses of the conjunction are interrupted by a sentence with another definition.
- Step (5) refers to quantifying over $X_0, \ldots, Q_l^i, \ldots$, which does not mean quantifying over $X_0, X_1, X_2, \ldots$; it means quantifying over $X_0, Q_1^1, \ldots, Q_l^i, \ldots, Q_{n(2)}^{m(n(2))}$.
The density of confusing exposition in this section is remarkable.