The positive solution uses an equivalent of the Axiom of Choice:
for every infinite set $A$ there is a bijection $f:A\to A\times A$.

In the basic Fraenkel Model (section 4.3 in Jech's Axiom of Choice) there
is an infinite set where there is no surjection as in the question.

Let $A$ be the infinite set of atoms in the model.

Step 1. Every subset of $A$ *in the model* is finite or cofinite.
Let $X\subseteq A$ and let $E\subseteq A$ be finite such that
$\operatorname{fix} E\subseteq\operatorname{sym} X$.
If $X\subseteq E$ then $X$~is finite.
If $X\not\subseteq E$ then $A\setminus E\subseteq X$:
fix $x\in X\setminus E$ and let $y\in A\setminus E$ be arbitrary;
the permutation~$\pi$ that interchanges $x$ and $y$ is in $\operatorname{fix} E$,
so $\pi X=X$, but this means that $y=\pi(x)\in\pi X=X$.

Step 2. Let $P$ be partition of $A$ *in the model* and
let $E\subseteq A$ be finite with $\operatorname{fix} E\subseteq \operatorname{sym} P$.
Assume there are $a$ and $b$ in $A\setminus E$ that are distinct
and $P$-equivalent.
Let $c\in A\setminus E$ be arbitrary and not equal to~$a$.
Let $\pi$ be the permutation that interchanges $b$ and $c$;
then $\pi\in\operatorname{fix} E$, hence $\pi P=P$.
Then $a,b\in X$ for some $X\in P$, and hence $a,c\in\pi X$.
As $\pi X\in\pi P=P$ this shows that $a$ and $c$ are $P$-equivalent as well.
It follows that either there is an element of $P$ that
contains $A\setminus E$, or all elements of $A\setminus E$ determine
one-element members of $P$.

Step 3. Assume $f:\mathcal{P}(A)\to\operatorname{Part}(A)$ is an order-preserving
surjection.
And let $E\subseteq A$ be finite such that $\operatorname{fix} E\subseteq\operatorname{sym} F$.

Assume $X$ and $Y$ are finite such that $X\cap E=Y\cap E$
and $|X\setminus E|=|Y\setminus E|$, *and* such that
$f(X)$ and $f(Y)$ are partitions that contain $\{\{a\}:a\in A\setminus E\}$.
Then $f(X)=f(Y)$.

To see this let $\pi$ be a permutation that
maps $X\setminus E$ to $Y\setminus E$ and vice versa and leaves all other
points in place.
Then $\pi\in\operatorname{fix} E$, so that $\pi(f(X))=f(X)$ and $\pi(f(Y)=f(Y)$.
The ordered pair $\langle X,f(X)\rangle$ is in $f$, hence
$\langle \pi(X),\pi(f(X))\rangle$ is in~$\pi f$, but $\pi f=f$ and $\pi X=Y$
so that $\langle Y,f(X)\rangle\in f$, that is, $f(Y)=f(X)$.

A similar statement holds when $X$ and $Y$ are infinite,
hence *cofinite*, and $X\cap E=Y\cap E$, and
$|A\setminus(E\cup X)|=|A\setminus(E\cup Y)|$.

Step 4. Now consider the set $\Pi(E)$ of partitions of~$A$ that contain
$\{\{a\}:a\in A\setminus E\}$; this is essentially the set of partitions
of~$E$ where each is augmented with $\{\{a\}:a\in A\setminus E\}$.

The argument above also shows the following: if $X$ and $Y$ are finite
such that $X\cap E=Y\cap E$, $|X\setminus E|\le|Y\setminus E|$
and $f(X),f(Y)\in\Pi(E)$ then $f(X)\le f(Y)$.
This is so because we can find a permutation $\pi$ in $\operatorname{fix} E$ such that
$\pi(X)\subseteq Y$.

Likewise: if $X$ and $Y$ are infinite such that
$X\cap E=Y\cap E$,
$|A\setminus(X\cup E)|\le|A\setminus(Y\cup E)|$
and $f(X),f(Y)\in\Pi(E)$ then $f(X)\ge f(Y)$.

Finally: if $X$ is finite and $Y$ is infinite such that
$X\cap E=Y\cap E$ and $f(X),f(Y)\in\Pi(E)$ then $f(X)\ge f(Y)$.

In conclusion: each subset of $E$ determines a chain in the set~$\Pi(E)$.

Step 5. If we enlarge $E$ then $\operatorname{fix} E$ becomes smaller, so we can choose
$E$ as large as we please.

Let $n$ be a natural number.
The number of partitions of the set $\{1,2,\ldots,4n\}$ into four sets
of size $n$ is equal to
$$
\binom{4n}{n}\binom{3n}{n}\binom{2n}{n}
$$
This number is larger than
$$
3^n\cdot 2^n\cdot\frac{4^n}{2n+1} = \frac{24^n}{2n+1}
$$
For $n\ge9$ we have $24^n/(2n+1)>16^n$.

This gives us our contradiction: if necessary enlarge $E$ so that $|E|=4n$
for some $n\ge9$.
Then, by 4 above, the map $f$ divides $\Pi(E)$ into,
at most, $2^{4n}=16^n$ chains.
On the other hand the partitions of $E$ into four pieces of size $n$ form an
antichain of cardinality more than $24^n/(2n+1)$, which in turn is
larger than $16^n$.

2more comments