First let me tackle the case of ordinals, with and without choice, then we can move on to non-well-orderable sets.
For the $\aleph$ numbers
The situation here is somewhat similar with and without choice, with a few minor points which diverge. First of all, the least $\lambda$ exists because as you point out $\kappa<2^{\kappa}$, so the class of ordinals satisfying $\kappa\leq2^\lambda$ is not empty, so there is a least one.
Easton's theorem, mentioned in an earlier answer, shows that if we start with $\sf GCH$, i.e. $2^\kappa=\kappa^+$ for all infinite $\kappa$, then any "reasonable function" can define the continuum function for regular cardinals in some extension of the universe which did not change cofinalities.
In Easton's construction we only talk about regular cardinals, not singular cardinals. And the singular cardinals in his construction take "the least possible value". For singular cardinals with uncountable cofinality, Silver showed that the behavior of the continuum function is dictated by the behavior below it "on a reasonably large set of points", but we can also prove that this reasonably large set can be taken to only contain singular cardinals with countable cofinality.
Shelah, Magidor, Gitik, Woodin, and many others showed that for cardinals with countable cofinality there's some we can say, but not a whole lot. For example, it is consistent that $\sf GCH$ holds below $\aleph_\omega$, and $2^{\aleph_\omega}=\aleph_{\alpha+1}$ where $\alpha$ is any (infinite) countable ordinal. But we don't know if it is possible for $\alpha$ to be $\omega_1$, for example. So it is hard to say what is the least $\lambda$ such that $2^\lambda\geq\aleph_{\omega_1}$ if we assume that $2^{\aleph_n}=\aleph_{n+1}$ for all $n<\omega$.
In general, the easy answer to your question, is we can't say anything for a given $\lambda$, since we can always push $2^{\aleph_0}$ to be at least as large as $\lambda$. It gets trickier if you define $\lambda$ in non-absolute terms, e.g. taking $\lambda=(2^{\aleph_0})^+$, so the meaning of $\lambda$ changes between models. But even then you can't say a whole lot more, because it's possible to have $2^{\aleph_0}=\lambda$ and for some uncountable and regular $\mu<\lambda$ make $2^\mu=\lambda^+$.
Without choice, though?
Well, if we assume the axiom of choice fails, then we can prove that there is a least $\kappa$ such that $2^\kappa$ is not an $\aleph$ anymore, in which case the $\leq$ immediately becomes $<$ for further cardinals. But we can also differentiate between "There is an injection from $\kappa$ into $2^\lambda$" and "There is a surjection from $2^\lambda$ onto $\kappa$". And those two are very different things.
The paper mentioned of Fernengel and Koepke deals with the surjections. There they show that pretty much the only restriction is that you need these to not decrease with the increase of $\lambda$. There's no requirement even on the cofinality. But they do not deal with the injection case.
When I was visiting Bonn a few years ago, I pointed out that it is possible to modify the construction to get some information also on the least $\kappa$ such that $\kappa\nleq2^\lambda$. Although here, since they do not use large cardinals and in fact their construction preserves cofinalities, we have more restrictions on what we can and cannot do. Of course, if you want to allow large cardinals in the mix, the whole things becomes significantly more complicated, and probably you can do almost anything as well.
But other than these small observations, the same things as before still hold. After all, just assuming choice fails does not tell us where in the universe it fails.
For arbitrary cardinals
Well, what about sets which cannot be well-ordered, then? That's a huge mess. First of all, you need to ask yourself what does "smallest" even mean? If there is a notion of "smallest" that means that the cardinals are well-ordered and choice holds.
So without choice you need to contend with the fact that there is no smallest. For example, if $A$ is amorphous, its power set is also Dedekind-finite. That means that if $B\subsetneq A$, then $2^B<2^A$, since $\mathcal P(B)\subsetneq\mathcal P(A)$.
But since either $B$ is finite, or $A\setminus B$ is finite, it is easy to show that $A<2^B$ for any infinite subset of an amorphous set (map $B$ to its singletons, and there are only finitely many points missing, which we can map to finitely many pairs, for example).
Also, you can't quite mix things here. If $A$ is amorphous, then it cannot be linearly ordered. But power sets of ordinals can always be linearly ordered. So there is no ordinal $\lambda$ such that $A\leq 2^\lambda$ to begin with. In the other direction, as remarked, $A$ has a Dedekind-finite power set, and so $\aleph_0\nleq 2^A$.
On the other hand, suppose that $A$ is an $\aleph_1$-amorphous set, namely every subset is countable or co-countable, and in a non-trivial way so every infinite subset of $A$ is Dedekind-infinite as well. In that case we can easily show that if $B\subseteq A$, then either $|A|=|B|$ or $|B|\leq\aleph_0$. But what can we say, in that case, about power sets? Not much, not much at all. We can't even say that $2^{\aleph_0}<2^A$ without additional assumptions.
The situation is in fact much worse without choice since we don't even understand how to control power sets of arbitrary sets in $\sf ZF$. We have no good understanding of forcing like a (generalised) Cohen forcing which does not add "bounded subsets", or even what it means for a cardinal to be regular or singular. The whole structure just immediately... breaks down.
In fact, even for $\aleph$ numbers if we wish to preserve the failure of the axiom of choice, then there is no forcing which is guaranteed to (1) add subsets to $\kappa$ without adding bounded sets, and (2) not make $2^\lambda$ well-orderable for any $\lambda<\kappa$. The only exception , of course, is $\kappa=\omega$, where we have Cohen reals to do the trick, mainly because finite sets have finite power sets anyway. (Things work out if $\operatorname{Add}(\kappa,1)$ is well-orderable, which is the same as saying that $\kappa^{<\kappa}$ can be well-ordered. But of course, that will fail at some point if the axiom of choice fails.)
In conclusion!
We can't say a whole lot. Sorry. And we can say even less if we want the axiom of choice to fail. And we can say a lot less if we want to focus on sets which cannot be well-ordered.
Best Answer
You are right, the case $\kappa = 0$ requires special attention. In that case we are looking at $0 \times \lambda$, which is just the cardinality of $\emptyset \times \lambda = \emptyset$. So $0 \times \lambda = 0$.
In particular, the inequality $\lambda \leq \kappa \times \lambda$ will not hold if $\kappa = 0$. But for any other $\kappa$ it will hold and your proof is correct.