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.
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$
Best Answer
This is (mostly) true.
In one direction, given $f:X\rightarrow X$, for each $a\in X$ we can consider the orbit of $a$ under $f$, $$orb_f(a)=\{f^{z}(a): z\in\mathbb{Z}\}.$$ If $X$ is Dedekind-finite, each $orb_f(a)$ must itself be finite, and by definition we have $f(orb_f(a))=orb_f(a)$ and $X=\bigcup_{a\in X}orb_f(a)$.
In the other direction, suppose $X$ is Dedekind-infinite. WLOG let $X=\mathbb{Z}\sqcup Y$. Then consider the self-bijection $f$ which shifts $\mathbb{Z}$ via $z\mapsto 1+z$ and is the identity on $Y$. Clearly we cannot partition $X$ into finite $f$-invariant pieces. However, at the same time we may still be forced to have some finite nonempty $f$-fixed sets: namely, if $Y$ itself is infinite but Dedekind-finite. So there is a slight subtlety there: the strong version of your property fully characterizes Dedekind-finiteness, but the weak version (the guaranteed existence of just one such $C$) doesn't.