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, 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}$.
Another interesting example occurs with the construction of two models of set theory $U$ and $W$ which agree on the arithmetic structure $\mathbb{N}^U=\mathbb{N}^W$, and have a subset $A\subset \mathbb{N}$ in common, such that $U$ thinks $A$ is arithmetic, but $W$ does not. There are many more similar such strange examples in the paper.
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 $i\in M$ and $N$ thinks that 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$. For example, the halting problem of $M$ or indeed any definable subset of $M$ becomes the initial segment of a computable and indeed pseudo-finite 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$
either generically, or 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\rangle$, 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.
