I know that $(\mathbb{N}, \cdot)$ and $(\mathbb{N}, |)$ are non automatic, but also not decidable. I also now that every automatic structure is decidable. Now I am curious if there is a non automatic structure, which is decidable, or if the previous sentence is iff.
A relational structure $\mathcal{A}$ is called automatic if there is a regular language $L$ and a surjective function $\nu: L \to A$ such that the following languages are regular:
$L_\epsilon := \{(w, w') \in L \times L | \nu(w) = \nu(w')\}$
$L_R := \{ w \in L^r | (\nu(w_1),...,\nu(w_r))\in R\}$ for all relations $R \subseteq A^r$
Contrary to your first sentence, arithmetic with just multiplication ("Skolem arithmetic") is decidable. (Compare with Presburger arithmetic, the also-decidable reduct of arithmetic to just addition.) In general, automaticity is a very strong structural property (consider e.g. the Constant Growth Lemma) and we can whip up decidable structures which are still "combinatorially nasty" and thus not automatic.