Let me answer your question as best I can; but I'll start by correcting a misconception in your question.
It actually never happens that "all units are powers of just one unit" except when the unit group is finite. The reason this happens is because $-1$ gets in the way! Suppose there's a unit $u$ such that every other unit $v$ can be written as $u^n$ for some $n \in \mathbf{Z}$. But $v = -1$ is a perfectly good unit, so we must be able to write $u^n = -1$; so this equation forces $u$ to be a root of unity, and in particular it can't generate an infinite group.
When the unit group is infinite, the best we can hope for is that there is a unit $u$ such that every unit $v$ is $u^n z$ where $z$ is a root of unity. This is precisely what happens for real quadratic fields: the fundamental unit $u$ has the property that every unit is $\pm u^n$ for some $n \in \mathbf{Z}$ (and you can't get rid of the $\pm 1$ there).
When $K$ has bigger degree you need more than one unit, and Dirichlet's unit theorem gives a precise formula for how many units you need. If the number field $K$ is generated by a single algebraic number $\theta$, then you look at the minimal polynomial of $\theta$ and count how many real and non-real roots it has: it will have $r$ real roots and $s$ conjugate pairs of non-real roots, for some $r$ and $s$. Dirichlet's theorem says that the smallest collection of units you need to get within a root of unity of every unit in $K$ is of size $r + s - 1$.
For instance, I'm particularly fond of the field $K = \mathbf{Q}(\sqrt[3]{2})$. The minimal polynomial of $\sqrt[3]{2}$ is $X^3 - 2$ which has one real root and two conjugate non-real roots; so in this case one unit suffices and the field $K$ does have a fundamental unit, which turns out to be $\sqrt[3]{2} - 1$.
On the other hand, the field $L = \mathbf{Q}(\sqrt[4]{2})$ corresponds to $X^4 - 2$, which has two real roots and one pair of conjugate roots; so we'll need $2 + 1 - 1 = 2$ units to generate everything -- there's no "fundamental unit" for $L$. There are computer programs for calculating in number fields, and my computer took approximately 0.07 seconds to tell me that if we take $u_1 = \sqrt[4]{2} + 1$ and $u_2 = \sqrt{2} - 1$ then every unit of $L$ is of the form $\pm u_1^a u_2^b$ for some $a, b \in \mathbf{Z}$.
PS: I will try and answer your updated questions.
You ask whether it wouldn't be better to take $\{ \sqrt[4]{2} + 1, \sqrt[4]{2} - 1\}$ rather than $\{ \sqrt[4]{2} + 1, \sqrt{2} - 1\}$ as "fundamental units". This is entirely a matter of taste: there's no really 'best' set to take, and lots of sets will work equally well. When $r + s -1$ is 1, then a fundamental $u$ will be unique up to replacing $u$ with $\omega \cdot u^{\pm 1}$ for $\omega$ one of the finite set of roots of unity in the field (usually just $\pm 1$); but as soon as you step to larger degrees there'll be an infinite amount of choice and it is a rather fruitless exercise to try and single out any one choice which is 'best'.
As for actually computing units in practice: the bible for such computations is Henri Cohen's book "A Course in Computational Algebraic Number Theory".
Here’s the story, though I leave it to others to furnish a proof or give a proper reference.
For $d\ge2$ and not a square, you get all solutions to the Pell equation $m^2-dn^2=\pm1$ by looking at the continued fraction expansion of $\sqrt d$. If $k=\lfloor\sqrt d\rfloor$, then your expansion looks like this:
$$
\sqrt d=k+\bigl[\frac1{\delta_1+}\>\frac1{\delta_2+}\cdots\frac1{\delta_{r-2}+}\>\frac1{\delta_{r-1}+}\>\frac1{2k+}\>\bigr]\,,
$$
where the part in brackets repeats infinitely. Then, every time you evaluate a convergent to the continued fraction just before the appearance of the $2k$, you’ll get a solution of Pell from the numerator $m$ and the denominator $n$. For instance, $\sqrt7=2+\frac1{1+}\,\frac1{1+}\,\frac1{1+}\,\frac1{4+}\,\cdots$, repeating with a period of length four. You evaluate $2+\frac1{1+}\,\frac1{1+}\,\frac1{1}=8/3$, and lo and behold, the first solution of $m^2-7n^2=\pm1$ is $m=8$, $n=3$.
For $d$ squarefree and incongruent to $1$ modulo $4$, this gives you all the units in $\Bbb Q(\sqrt{d}\,)$, but for $d\equiv1\pmod4$, it may happen that what you get is the cube of a unit. But as I recall, in that case, the primitive unit’s coordinates always will show up as the numerator and denominator of an earlier convergent.
Best Answer
In the case of a real quadratic field, the fundamental unit is the smallest unit of the form $ x + y \sqrt{d} $ such that $ x \geq 0 $ and $ y \geq 1 $. To see this, note that if $ x + y \sqrt{d} > 1 $ is a unit, we have that $ x^2 - dy^2 = \pm 1 $. Assume that $ x $ and $ y $ had different signs, then we would have
$$ x + y \sqrt{d} = \frac{\pm 1}{x - y \sqrt{d}} $$
and $ |x - y \sqrt{d}| \geq 1 $ since $ x $ and $ -y $ have the same sign. This is a contradiction, therefore $ x $ and $ y $ are both nonnegative in $ x + y \sqrt{d} $. Since the fundamental unit is the smallest unit greater than $ 1 $, it follows that we may simply look at units of the form $ x + y \sqrt{d} $ where $ x, y $ are nonnegative, which reduces the problem to a necessarily finite brute force search.
While Dirichlet's unit theorem necessarily implies that the above found unit must be the fundamental unit, there is a more elementary proof of this fact. Assume that $ \varepsilon $ is the smallest unit greater than $ 1 $, and $ x $ is any unit greater than $ 1 $. We want to show that $ x $ is a power of $ \varepsilon $. Since the sequence $ a_n = \varepsilon^n $ diverges, there is a greatest integer $ n $ such that $ a_n = \varepsilon^n \leq x $. Then, $ x/\varepsilon^n $ is a unit $ \geq 1 $, but it is less than $ \varepsilon $ since $ x < \varepsilon^{n+1} $. By the definition of $ \varepsilon $, the only unit in the interval $ [1, \varepsilon) $ is $ 1 $, so it follows that $ x = \varepsilon^n $.
A more sophisticated algorithm to find the fundamental unit involves continued fractions, see these lecture notes for further information.