$\omega + \omega$ is at most countable although it is not order isomorphic to $\omega$: order type and cardinality are different invariants

The ordinal $\omega + \omega$ is at most countable as a set (Finite, countably infinite, countable, uncountable), and it is not order isomorphic to $\omega$ (Order embedding and order isomorphism).

There is no tension. Countability is a statement about bijections and ignores order; order type is a statement about order isomorphisms and is finer. Two well-orders on the same countably infinite set can have different order types: $\omega$ and $\omega + 1$ already show it, as the first example of this page records, and $\omega$ and $\omega + \omega$ show it with the two copies visible.

$\omega + \omega \;=\; \mathrm{ot}\big(\underbrace{0, 1, 2, \dots}_{\text{first copy}} \ \ \underbrace{0', 1', 2', \dots}_{\text{second copy}}\big).$

How far this goes. Every ordinal strictly below $\omega_1$ is at most countable ($\omega_1$ is uncountable, every ordinal below it is at most countable, it is a cardinal and a limit ordinal, and its existence is a theorem of ZF), and there are a great many of them: $\omega + \omega$ and $\omega \cdot \omega = \omega^{2}$ are at most countable by the argument above, and no two distinct ordinals are isomorphic as orders. So a single countably infinite set carries uncountably many mutually non-isomorphic well-orders, one for each infinite ordinal below $\omega_1$. Nothing here says the same of $\omega^{\omega}$ or of $\varepsilon_0$ ($\omega^{2}$, $\omega^{\omega}$, and $\varepsilon_0 = \sup\{\omega, \omega^{\omega}, \omega^{\omega^{\omega}}, \dots\}$ satisfying $\omega^{\varepsilon_0} = \varepsilon_0$): those are ordinals of larger order type, and their cardinality is a question no item on these pages settles, as that item's last remark records.

Why the argument does not need a choice principle. The bijection used at step 2.1 is the collapsing isomorphism of Every well-order has a unique order type, which is unique and therefore never chosen, and A product of two at most countable sets is at most countable is choice free too. Countability of a countable union of countable sets is a different matter and does cost $\mathrm{AC}_\omega$; that is Countable unions of at most countable sets, assuming $\mathrm{AC}_\omega$ and it is not used here.

The confusion this item exists to prevent. "$\omega + \omega$ is bigger than $\omega$" is true as a statement about ordinals, where bigger means further along the ordinal order, and false as a statement about size. The two readings of "bigger" are exactly order type and cardinality.