Does $k+\aleph_0=\mathfrak{c}$ imply $k=\mathfrak{c}$ without the Axiom of Choice?

There is a general argument without choice: Suppose ${\mathfrak m}+{\mathfrak m}={\mathfrak m}$, and ${\mathfrak m}+{\mathfrak n}=2^{\mathfrak m}$. Then ${\mathfrak n}=2^{\mathfrak m}.\,$ This gives the result.

The argument is part of a nice result of Specker showing that if CH holds for both a cardinal ${\mathfrak m}$ and its power set $2^{\mathfrak m}$, then $2^{\mathfrak m}$ is well-orderable. This shows that GCH implies choice, and that the proof is "local". It is still open whether CH for ${\mathfrak m}$ implies that ${\mathfrak m}$ is well-orderable.

Anyway, here is the proof of the statement above: Note first that $2^{\mathfrak m}\cdot 2^{\mathfrak m}=2^{{\mathfrak m}+{\mathfrak m}}=2^{\mathfrak m}={\mathfrak m}+{\mathfrak n}$.

Let $X$ and $Y$ be disjoint sets with $|X|={\mathfrak m}$, $|Y|={\mathfrak n}$, and fix a bijection $f:{\mathcal P}(X)\times{\mathcal P}(X)\to X\cup Y$.

Note that there must be an $A\subseteq X$ such that the preimage $f^{-1}(X)$ misses the fiber $\{A\}\times {\mathcal P}(X)$. Otherwise, the map that to $a\in X$ assigns the unique $A\subseteq X$ such that $f^{-1}(a)$ is in $\{A\}\times {\mathcal P}(X)$ is onto, against Cantor's theorem.

But then, for any such $A$, letting $g(B)=f(A,B)$ gives us an injection of ${\mathcal P}(X)$ into $Y$, i.e., $2^{\mathfrak m}\le {\mathfrak n}$. Since the reverse inclusion also holds, we are done by Schroeder-Bernstein.

(Note the similarity to Apostolos's and Joriki's answers.)

The original reference for Specker's result is Ernst Specker, "Verallgemeinerte Kontinuumshypothese und Auswahlaxiom", Archiv der Mathematik 5 (1954), 332–337. A modern presentation is in Akihiro Kanamori, David Pincus, "Does GCH imply AC locally?", in "Paul Erdős and his mathematics, II (Budapest, 1999)", Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, (2002), 413–426.

Note that assuming that ${\mathfrak m}$ is infinite is not enough for the result. For example, it is consistent that there are infinite Dedekind finite sets $X$ such that ${\mathcal P}(X)$ is also Dedekind finite. To be Dedekind finite means that any proper subset is strictly smaller. But if $2^{\mathfrak m}$ is Dedekind finite and $2^{\mathfrak m}={\mathfrak n}+{\mathfrak l}$ for nonzero cardinals ${\mathfrak n},{\mathfrak l}$, then we must have ${\mathfrak n},{\mathfrak l}<2^{\mathfrak m}$.

Given a set $K$ with $\lvert K \rvert=k$ and a bijection $f:\mathbb{R}\to K\cup \mathbb{N}$ (assuming without loss of generality that $K$ is disjoint from $\mathbb{N}$), pick some $x\in\mathbb{R}$ such that $f$ maps no element of $x+\mathbb{N}\subset\mathbb{R}$ to $\mathbb{N}$ (this is just one choice and it's possible since only countably many elements are mapped to $\mathbb{N}$), and define a bijection $g:\mathbb{R}\to K$ by mapping $f^{-1}(\mathbb{N})$ to $f(x+2\mathbb{N})$, mapping $x+\mathbb{N}$ to $f(x+1+2\mathbb{N})$, and mapping $\mathbb{R}\setminus\left((x+\mathbb{N})\cup f^{-1}(\mathbb{N})\right)$ as in $f$. This bijection establishes without choice that $k=\lvert K \rvert=\lvert\mathbb{R}\rvert=\mathfrak{c}$.

There's another way apart from joriki's answer that I think is a bit easier and is usually considered the "standard" way to show what you are asking:

First of all we have that $\mathfrak{c}\times\mathfrak{c}=\mathfrak{c}$. To see this using subsets of natural numbers (for example) observe that given $X,Y\in\mathcal{P}(\omega)$ the function $(X,Y)\mapsto\{2n : n\in X\}\cup\{ 2n+1 : n\in Y\}$ is an injection.

Thus we need to show that given a countable set $X\subset\mathbb{R}\times\mathbb{R}$ we have that $|\mathbb{R}\times\mathbb{R}\setminus X|=\mathfrak{c}$. Take the projection of $X$, $\pi(X)$. $\pi(X)$ is at most countable. This doesn't use the axiom of choice since $X$ is well orderable (because it's countable). Therefore, there exists $x\in\mathbb{R}$ such that $x\notin\pi(X)$. Then the set $\{x\}\times\mathbb{R}$ (that has cardinality $\mathfrak{c}$) is disjoint from $X$ and thus a subset of $\mathbb{R}\times\mathbb{R}\setminus X$. Apply Cantor-Bernstein theorem and you are done.