The two definitions are certainly not equivalent.
Suppose that $A$ is any infinite Dedekind-finite set. Let $S$ be the set of finite injective sequences from $A$, namely, all the injective functions from a natural number into $A$.
Claim. $S$ is Dedekind-finite.
Proof. Suppose not, then we have a countably infinite subset of sequences, $f_n$ for $n<\omega$, and without loss of generality $f_n\neq\varnothing$ for all $n<\omega$ as well, otherwise just omit that one empty function. Define the following function by recursion $F(0)=f_0(0)$; $F(n+1)=f_n(k)$ where $n$ is the least such that for some $k\in\operatorname{dom}(f_n)$, $F(i)\neq f_n(k)$ for all $i\leq n$. This is well-defined since the first $n$ functions enumerated only a finite union of finite sets, and there are only finitely many injections from a finite ordinal into a finite set, so there will be some $n$ and $k$.
In other words, go through the functions in order, and along their domains, in order, and when you find a new element you've not encountered before, add it to your list.
Easily, $F$ is injective and with domain $\omega$. So $A$ must be Dedekind-infinite, which is a contradiction. So, indeed, $S$ is Dedekind-finite. $\square$
Claim. There is a surjection from $S$ onto itself which is not a bijection.
Proof. Let $f\in S$, if $f=\varnothing$, then $f\mapsto f$; otherwise, the domain of $f$ is some $n+1$, simply define $f\mapsto f\restriction n$. In other words, remove the last point from each sequence, if such point exists.
Easily, this function is a surjection, and it is certainly not a bijection since any $1$-tuple is mapped to the empty function, as well as the empty function itself.
So, what we have shown is that if there is any kind of Dedekind-finite set, then there is one which is $*$-Dedekind-infinite.
To your second question, since you've proved the equivalences of all the others, let me use that.
Assuming (2), or equivalently (4), we can take either $B$ to be a proper subset of $A$ of the same cardinality, or $A=\cup\{x\}$ for some $x\notin A$. So we get the case that $B\subsetneq A$ or $A\subsetneq B$, respectively. In both cases, exactly one of $A\setminus B$ and $B\setminus A$ is empty.
So (1)–(4) all imply (5).
In the other direction, assume that there is no bijection between $A\setminus B$ and $B\setminus A$ and let $f\colon A\to B$ be a bijection.
Then we know that either there is some $a\in A\setminus B$ such that $f(a)\in A\cap B$ or there is some $b\in B\setminus A$ such that $f^{-1}(b)\in A$. Since otherwise, $f\restriction A\setminus B\to B\setminus A$ would have been a bijection.
Let's consider all the images and preimages of points in $A$ that are in $A$; and let's do the same for those in $B$ (by $f^{-1}$). So given a point $a\in A$, if $f(a)\in A$, or $f^{-1}(a)\in A$, we will chart that course. Once we've hit $B\setminus A$ or $A\setminus B$, we stop. Now let's consider our cases.
There is some $a\in A$ with an infinite orbit. In this case, we have (3) holds, so $A$ is Dedekind-infinite.
There are no infinite orbits. But if $a\in A\setminus B$ or $b\in B\setminus A$, then the orbits of $a$ and $b$ must not only be finite, but linear and satisfy these two properties:
If $f^n(a)$ is the last point in the orbit, then $f^{n+1}(a)\in B\setminus A$. Otherwise, we can continue and apply $f$ for longer.
If $a\notin A\setminus B$, then it is the only point in that orbit satisfying that property. Because $f\colon A\to B$, it is impossible for a point in $A\setminus B$ to be in the image of $f$.
The two properties have versions for $b\in B\setminus A$, of course. However, what it means is that we can identify for each $a\in A\setminus B$, some $b\in B\setminus A$ which is uniquely determined by some finitely many applications of $f$. In other words, $f$ determines an injection from $A\setminus B$ into $B\setminus A$, and likewise $f^{-1}$ determines an injection in the other direction. By Cantor–Bernstein, this means that $A\setminus B$ and $B\setminus A$ have the same cardinality.
Therefore, either $A$ is Dedekind-infinite, or $A\setminus B$ and $B\setminus A$ have the same cardinality. Since we assumed the latter failed, it must be that the former holds. $\square$
Referring to Theorem to 4.21, Proposition 4.22 In L. Halbeisen's book as explained in the comment:
Let $A$ be an infinite set.
Let $\text{fin}(A)$ be the finite subsets of $A$, $\text{cof}(A)$ the cofinite subsets of $A$. Write $\mathcal P(A)=\text{fin}(A)\sqcup\text{cof}(A)\sqcup \text{binf}(A)$, where $\text{binf}(A)$ is the rest.
If $|\mathcal P(A)\setminus \text{fin}(A)|=|\text{fin}(A)|$ then $|\mathcal P(A)|=2|\text{fin}(A)|$.
Now assume $A$ is not amorphous (so $\text{binf}(A)\ne\emptyset$) and $|\mathcal P(A)\setminus \text{fin}(A)|=|\text{fin}(A)|$. Let $\sigma\colon\mathcal P(A)\setminus \text{fin}(A)\to\text{fin}(A)$ be a bijection. Let $\tau\colon \mathcal P(A)\setminus\text{cof}(A)\to\text{fin}(A)$ be defined by
$$
\tau(x)=\begin{cases}
\sigma(A\setminus x)&x\in\text{fin}(A)\\
\sigma(x)&x\in\text{binf}(A)
\end{cases}
$$
Then $\tau$ is a bijection. Let $u\in\text{binf}(A)$. Then $\tau(u)\in\text{fin}(A)$, so $\tau(u)\not\in\tau(\text{fin}(A))$. Therefore $\tau\rvert_{\text{fin}(A)}$ is an injective map from $\text{fin}(A)$ onto a proper subset of itself. Therefore $\text{fin}(A)$ is Dedekind infinite (i.e. $\aleph_0\le|\text{fin}(A)|$.)
Now consider the proof of Prop 4.22. The restriction that $n$ not be a power of two is only used in the previous-to-last paragraph, and it's used to show that under the assumptions of the proposition (which permit amorphous!) $\aleph_0\le|\text{fin}(A)|$. Once that is shown, what's described in the last paragraph is applicable to any $n$, including powers of $2$. In the present case we have $|\mathcal P(A)|=n|\text{fin}(A)|$ where $n=2$. The last paragraph describes how to modify the proof of Theorem 4.21 (which is fairly complicated) to get a contradiction by injecting $\text{Ord}$ into $\text{fin}(A)$. So for any infinite $A$ for which $\aleph_0\le|\text{fin}(A)|$, it follows that $|\mathcal P(A)|\ne n|\text{fin}(A)|$ for any $n\ge 1$.
Best Answer
Introducing new sets is just confusing. You have a set $D$ with a partition into pairs, say $P$, and a partition into pairs + a singleton, call it $O$. Let's call that singleton $\{d\}$.
Now we will define the following function:
$f(d)=a_0$ such that $\{a_0,d\}\in P$. This $a_0$ exists, and it is not $d$ itself, of course, since $P$ is a partition into pairs. Next, $f(a_0)=a_1$ such that $\{a_0,a_1\}\in O$, this $a_1$ exists since the unique singleton in $O$ was $\{d\}$ and $d\neq a_1$.
And so we proceed: $f(a_{2n+1})=a_{2n+2}$ such that $\{a_{2n+1},a_{2n+2}\}\in O$ and $f(a_{2n+2})=a_{2n+3}$ such that $\{a_{2n+2},2_{2n+3}\}\in P$.
But wait, what have we done??? This is really a function from $\Bbb N$ into $D$. And it is injective!
So $D$ is Dedekind-infinite.