Without using the AC, show that if $\kappa \geq \aleph_0$ then $2^{\kappa}-\kappa=2^{\kappa}$. That is to say, for such $\kappa$ there is a unique cardinal $\mu$ such that $\kappa+\mu=2^{\kappa}$, and this $\mu$ equals $2^{\kappa}$.
In Rubin & Rubin, "Equivalents of the Axiom of Choice", 2nd edition, 1985, this is mentioned as a well-known property of cardinals (cf. Theorem 0.14.f in the book), but sadly they do not provide a proof.
Found a proof for the case $\kappa=2\kappa$.
Lemma: for any cardinals $\kappa,\mu,\lambda$, if $\kappa+\mu=\lambda=\lambda^{2}$ then either there is a surjection of $\kappa$ onto $\lambda$, or we have $\mu=\lambda$.
Proof: if $f:\kappa\sqcup\mu\to\lambda^{2}$ is a bijection (with $\sqcup$ denoting disjoint union), let $g:\kappa\to\lambda$ be the map $\pi_1\circ (f\upharpoonright\kappa)$, where $\pi_{1}:\lambda^{2}\to\lambda$ is the projection on the first factor (i.e. $\pi_{1}(x,y)=x$ for $x,y\in\lambda$). If $g$ is surjective, we are done. If not, $\exists{z\in\lambda}$ such that $(\{z\}\times\lambda)\cap f[\kappa]=\varnothing$. But then we have $\{z\}\times\lambda\subseteq f[\mu]$, since f is a surjection, and so $\lambda\leq\mu$; since $\mu\leq\lambda$ also holds, we find $\mu=\lambda$, q.e.d.
Now if $\kappa+\mu=2^{\kappa}$, for a $\kappa$ with $\kappa=2\kappa$, apply the Lemma with $\lambda=2^{\kappa}$; one has $\lambda=\lambda^{2}$ in view of $\kappa=2\kappa$, and a surjection of $\kappa$ onto $\lambda=2^{\kappa}$ cannot exist (Cantor). It follows that $\mu=2^{\kappa}$.
You can prove it this way : $2^\kappa \leq 2^\kappa + \kappa \leq 2^\kappa + 2^\kappa \leq 2^\kappa \times 2 \leq 2^{\kappa+1}\leq 2^\kappa$
The first inequality comes from the natural injection, The second as well,where there is an injection $\kappa \to 2^\kappa$, sending $x\to \{x\}$ The third one comes from identifying the disjoint union of $A$ and $B$ as $A\times\{0\}\cup B\times\{1\}$ The fourth one is the natural injection, And the last one is simply that, $\kappa$ being infinite, $\kappa +1 \leq \kappa$.
By Cantor-Bernstein's theorem, all these inequalities of cardinals (i.e. injections) can be turned into equalities of cardinals, that is, bijections.
Therefore $2^\kappa +\kappa \sim 2^\kappa$
Now if you take $A$ to be a subset of $2^\kappa$ of cardinality $\kappa$, then you can use this bijection to produce a bijection $2^\kappa \setminus A\to 2^\kappa$.
EDIT : It seems Noah Schweber was quicker
Second edit: The last sentence of this answer is there to show the uniqueness of $\mu$: assume $\kappa + \mu = 2^\kappa$. Then the image of $\kappa$ under a bijection $\kappa + \mu \to 2^\kappa$ is a subset $A\subset 2^\kappa$ of cardinality $\kappa$. But $2^\kappa\setminus A$ is the image of $\mu$ o has cardinality $\mu$. But according to my last sentence it also has cardinality $2^\kappa$, which proves that $2^\kappa \sim \mu$. I'm adding this to my answer because Matthé Van der Lee commented on Noah's answer saying that the uniqueness of $\mu$ hadn't been established.