If two models of set theory $U$ and $W$ have the same arithmetic
structure $\langle\mathbb{N},+,\cdot,0,1,<\rangle$, then as you
observe the operation of Turing machines will be absolute between
$U$ and $W$, and so they will think precisely the same sets are
decidable. Furthermore, they will agree on the members of any
arithmetic set defined by a standard-length formula $\varphi$.

Things get very interesting, however, if one considers the possibly nonstandard-length arithmetic formulas from inside the models, and in this case it is not correct to say that $U$ and $W$ must agree on all sets
that *they* think are arithmetic. For example, in my
paper, [Satisfaction is not absolute](http://jdh.hamkins.org/satisfaction-is-not-absolute/), joint with Ruizhi Yang,
we prove a number of instances of such models of set theory
disagreeing on what they think is arithmetic truth.

One interesting example there occurs when two models $U$ and $W$
of ZFC have the same natural numbers $\mathbb{N}^U=\mathbb{N}^W$ and the same arithmetic structure, and have a
Turing machine program $e$  that computes a relation $\lhd$ on
$\mathbb{N}$, which both $U$ and $W$ think is a linear order on
$\mathbb{N}$, but $U$ thinks it is well ordered and $W$ thinks it
is not well ordered. So the two models agree on all Turing machine computations, but they disagree on the computable ordinals and on $\omega_1^{CK}$. 

Meanwhile, the answer to your question at the end is affirmative.

**Theorem.** If $M$ is any countable model of PA, and $A\subset M$
is a set such that $\langle M,+,\cdot,A\rangle\models\text{PA}^*$,
meaning that it satisfies induction in the expanded language, then
there is an elementary end-extension $M\prec N$ such that $A$ is
coded in $N$, in the sense that there is some $a\in N$ such that
$i\in A$ if and only if the $i^{th}$ prime $p_i$ divides $a$ in
$N$.

Thus, even though the set $A$ might not be computable in $M$, it
becomes the initial segment of a computable set in $N$.

The theorem can be proved by means of a definable ultrapower of
$\langle M,+,\cdot,A\rangle$. One defines the $M$-ultrafilter $U$
in $\omega$ many steps so that every function $f:M\to M$ that is
definable in that structure and bounded by an element of $M$ is
constant on a set in $U$. It follows that the ultrapower $N$,
using all definable functions in $\langle M,+\cdot,A\langle$, is
an elementary top-extension, and $A$ will be coded since we may
define the function coding longer and longer pieces of $A$.

We can also arrange that these models arise as the $\mathbb{N}$ of models of ZFC.