Rudin's proof on the uniqueness of a power root This is a snapshot of Baby Rudin:

Theorem For every real $x>0$ and every integer $n>0$ there is one and only one positive real $y$ such that $y^n=x$.
This number $y$ is written $\sqrt[n]{x}$ or $x^{1/n}$.
Proof That there is at most one such $y$ is clear, since $0<y_1<y_2$ implies $y_1^n<y_2^n$.
Let $E$ be the set consisting of all positive real numbers $t$ such that $t^n<x$.
If $t=\frac{x}{1+x}$ then $0\le t<1$. Hence $t^n\le t<x$. Thus $t\in E$, and $E$ is not empty.
If $t>1+x$ then $t^n\ge t>x$, so that $t\notin E$. Thus $1+x$ is an upper bound of $E$.
Hence Theorem 1.19 implies the existence of
$$y=\sup E$$
To prove that $y^n=x$ we will show that each of the inequalities $y^n<x$ and $y^n>x$ leads to a contradiction.
The identity $b^n-a^n=(b-a)(b^{n-1}+b^{n-2}a+\cdots+a^{n-1})$ yields the inequality
$$b^n-a^n<(b-a)nb^{n-1}$$
when $0<a<b$.
Assume $y^n<x$. Choose $h$ so that $0<h<1$ and
$$h<\frac{x-y^n}{n(y+1)^{n-1}}$$
Put $a=y,b=y+h$. Then
$$(y+h)^n-y^n<hn(y+h)^{n-1}<hn(y+1)^{n-1}<x-y^n$$
Thus $(y+h)^n<x$, and $y+h\in E$. Since $y+h>y$, this contradicts the fact that $y$ is an upper bound of $E$.
Assume $y^n>x$. Put
$$k=\frac{y^n-x}{ny^{n-1}}$$
Then $0<k<y$. If $t\ge y-k$, we conclude that
$$y^n-t^n\le y^n-(y-k)^n<kny^{n-1}=y^n-x$$
Thus $t^n>x$, and $t\notin E$. If follows that $y-k$ is an upper bound of $E$.

To get the definition of $h$, I understand we need $x-y^n$ in the denominator to make the whole thing greater than $0$, but where does the denominator $n(y+1)^{n-1}$ come from?
The same question on the form of $k$. Why do we need such a denominator $ny^{n-1}$?
 A: Rudin follows the mathematical style of writing his 'probe for the proof' on a piece of scrap paper, and upon arriving at the solution, writing up a formal and terse proof that hides the 'mathematical eyebrow sweat' that went behind it.
The $\text{1.21 Theorem}$ the OP is analyzing comes right after Rudin introduces the real numbers as a complete ordered field in Chapter 1; the solution there can only use the developed axiomatic machinery.
Let us probe this matter and work up some 'sweat'.
We have our fixed positive real number $x$ and an integer $n \gt 0$. In general the only easy thing is to find a real number $a \gt 0$ such that
$\tag 1 a^n \lt x$
Can we do better? Can we 'make $a$ larger' so that $\text{(1)}$ still holds?
Suppose $b \gt a$. How do we 'enforce' the condition that $b^n \lt x$?
$\tag 2 [ b^n \lt x ] \text{ iff } [ (b^n - a^n + a^n) \lt x ] \text{ iff } [ (b^n - a^n) \lt (x - a^n) ]$
It may take you a page or two of scrap paper to discover that the key to solving this is that
$\tag 3 b^n-a^n<(b-a)nb^{n-1}$
is always true with $0 \lt a \lt b$. So by setting up some bound $M$ and with $b = a + h$, you can write
$\tag 4 b^n \lt h M + a^n \lt hM + x$
Geometrically, Rudin knows that $E$ is an interval. The set $F$ of real positive numbers $u^n \gt x$ is also an open interval. The supremum of $E$ is equal to the infimum of $F$.
The above describes the conceptual thinking behind Rudin's proof (no calculus allowed).

The following theory gets the result in a different manner, and proposition 2 clarifies part of Rudin's argument in his proof construction.
Let $x$ be some fixed positive real number and $n \in {\mathbb Z}^+$.
Proposition 1: Let $D \subset (0, +\infty)$ be a nonempty set of real numbers and assume that for any $d \in D$, $d^n \gt x$. Then $[\text{inf(D)}]^n \ge x$.
Proof
Let $y = \text{inf(D)}$ and to arrive at a contradiction, assume that $y^n \lt x$. Choose $h$ so that $0<h<1$ and
$\quad h<\frac{x-y^n}{n(y+1)^{n-1}}$
Set $a=y$ and $b=y+h$. Then, using Rudin's (3) from the prior section,
$\quad (y+h)^n-y^n<hn(y+h)^{n-1}<hn(y+1)^{n-1}<x-y^n$
But then $(y+h)^n<x$ and so $y + h$ must be a lower bound for $D$. Yet it is greater than $y$ which is the $\text{glb}$, a contradiction. $\blacksquare$
Proposition 2: Let $D \subset (0, +\infty)$ be a nonempty set of real numbers and assume that for any $d \in D$, $d^n \lt x$. Then $[\text{sup(D)}]^n \le x$.
Proof
Let $y = \text{sup(D)}$ and to arrive at a contradiction, assume that $y^n \gt x$. Set
$\quad h=\frac{y^n-x}{ny^{n-1}}$
It is easy to see that $0 \lt h \lt y$. 
Set $a=y-h$ and $b=y$. Then, using Rudin's (3) from the prior section,
$\quad y^n-(y-h)^n<hny^{n-1}= y^n-x$
But then $(y-h)^n>x$ and so $y - h$ must be an upper bound for $D$. Yet it is smaller than $y$ which is the $\text{lub}$, a contradiction. $\blacksquare$
Let $E = \{t \gt 0 \, | \, t^n \lt x \}$ and $F = \{t \gt 0 \, | \, t^n \gt x \}$.
Proposition 3: $\text{sup(E)} = \text{inf(F)}$ and if we denote this number by $\gamma$, then $\gamma^n = x$.
Proof
Let $\beta = \text{inf(F)}$. By proposition 1, $\beta^n \ge x$.
Let $\alpha = \text{sup(E)}$. By proposition 2, $\alpha^n \le x$.
Since $\beta$ is an upper bound for $E$, $\alpha \ge \beta$.
Since $\alpha$ is an lower bound for $F$, $\alpha \le \beta$.
So $\alpha = \beta$ and the proposition follows. $\blacksquare$

In a comment the OP had a question on how to derive the inequality. To be complete, even if it is no longer necessary, consider this:
The identity $b^n-a^n=(b-a)(b^{n-1}+b^{n-2}a+\cdots+a^{n-1})$ yields the inequality
$b^n-a^n<(b-a)nb^{n-1}$
when $0<a<b$.
We have $n$ terms in $b^{n-1}+b^{n-2}a+\cdots+b^0 a^{n-1}$, but since $a \lt b$,
$|b^{n-1}a^0+b^{n-2}a^1+\cdots+b^0 a^{n-1}| \lt |b^{n-1}a^0|+|b^{n-2}a^1|+\cdots+|b^0 a^{n-1}| \lt$
$\quad |b^{n-1}|+|b^{n-1}|+\cdots+|b^{n-1}| \lt n b^{n-1}$

In his question, the OP ask where does the denominator come from in 
$\quad h<\frac{x-y^n}{n(y+1)^{n-1}}$
This is the same thing as working with an $[\varepsilon , \delta]$ proof in calculus. After the 'probing', we set $h$ (like we do with $\delta$) to what works and shows that we can control the quantities. In essence, we are using the fact that the function $f(x) = x^n$ is continuous, but the book still hasn't discussed that concept.
A: In a comment I offered to give a different proof. The proposer accepted, on condition that it is simpler. Whether this is simpler, or not, is not for me to say.
Let $x>0$ and $n\in \Bbb Z^+.$ We show $\exists y\in \Bbb R^+\;(y^n=x).$
Lemma 1. For any $n\in \Bbb N$ we have $\forall r>0\;\exists s>0\;(\;1+r>(1+s)^n\;).$
Proof:  Let $0<s<2^{-n}\min (1,r)).$ (For example let $s=2^{-n-1}\min (1,r)$.) For $1\leq j\leq n$ we have $0<\binom {n}{j}s^j\leq \binom {n}{j}s.$ So we have $(1+s)^n=$ $1+\sum_{j=1}^n\binom {n}{j}s^j\leq$ $ 1+\sum_{j=1}^n\binom {n}{j}s=$ $1+(2^n-1)s<$ $1+(2^n-1)2^{-n}r<1+r.$
Corollary 1 .  If $y>0$ and $y^n>x$ then $\exists q\in \Bbb Q^+\cap (0,y)\;(q^n>x).$
Proof: Let $y^n=x(1+r).$  By Lemma 1 let $s>0$ such that $1+r>(1+s)^n.$ Let $q\in \Bbb Q^+\cap (y/(1+s),y).$ Then    $1<(1+r)(1+s)^{-n}<1+r.$ So we have  $x<x(1+r)(1+s)^{-n}=y^n(1+s)^{-n}=(y/(1+s))^n<q^n.$
Lemma 2.  If $y>0$  and $y^n<x$ then $\exists q\in \Bbb Q \cap (y,\infty)\;(q^n<x).$ 
Proof: Let $y'=1/y.$ Let $x'=1/x.$ Let $(y')^n=(x')^{-1}(1+r).$ By Corollary 1 there exists  $q'\in \Bbb Q \cap (0,y')\;( (q')^n>x').$ Now let  $q=1/q'.$
Part 3. By the construction of $\Bbb R$ by Dedekind cuts on $\Bbb Q,$ if $A,B$ are non-empty subsets of $\Bbb Q$ such that $A\cup B=\Bbb Q$ and such that $\forall a\in A\;\forall b\in B\;(a<b)$ then there is a unique $y\in \Bbb R$ such that $y=\sup A=\inf B.$
Let $A=(\Bbb Q\cap (-\infty,0])\cup \{q\in \Bbb Q^+: q^n<x\}.$ Let $B=\{q\in \Bbb Q^+: q^n\geq x\}.$ Let $y=\sup A=\inf B.$
We have $y>0$ because if $q\in (0, \min (1,x)\cap \Bbb Q$ then $q^n\leq q<x$ so $q\in A$ so $y=\sup A\geq q>0.$ 
If $y^n>x$ then by Corollary 1, $\exists q\in Q^+\cap (0,y)\;(q^n>x),$ contrary to $y=\inf B.$
If $y^n<x$ then by Lemma 2, $\exists q\in \Bbb  Q^+\cap (y,\infty)\;(q^n<x),$ contrary to $y=\sup A.$ 
Therefore $y^n=x.$ QED.
NOTES: Since $\Bbb Q$ is order-dense (in itself) (i.e. there is a rational strictly between any 2 rationals), it follows by the construction of $\Bbb R$ from $\Bbb Q$ by Dedekind cuts that there is a rational strictly between any 2 reals, which was used to obtain $q$ in the proof of Corollary 1, and also in Part 3 to show that $y>0$. We also used, throughout, that $\forall a,b>0\;\forall n\in \Bbb Z^+\;(a<b\iff a^n<b^n).$ In Part 3 we have $B\ne \emptyset$ because (again by the construction of $\Bbb R$ ) $\exists q\in \Bbb Z^+ \;(q>\max (1,x))$ so $q^n\geq q>x$ so $q\in B.$
A: The $n(y+1)^{n-1}$ is an arbitrary inclusion carefully crafted to cancel out the denominator in the inequality $\ldots hn(y+1)^{n-1} < \frac{x-y^n}{n(y+1)^{n-1}}n(y+1)^{n-1}=x-y^n$. Like you said, since $x-y^n > 0$, $h$ is still between 0 and 1, even when we add the new restriction.
Same goes for $k$. 
A: As DanielWainfleet shows, you are well on you way if you can show that when $y^n \lt x$ you can find an $s \gt 0$ such that ${(y+s)}^n \lt x$. Also, the rest of his argument can be rewritten using only Rudin's axiomatic definition of $\mathbb R$ (no reason to mention Dedekind cuts).
Proposition: Let $x \gt 0$ and $n$ a positive integer. Suppose $y \gt 0$ and $y^n \lt x$. Then there exists a positive real number $s$ such that ${(y+s)}^n \lt x$.
Proof
We have
$\tag 1 {(y+s)}^n =y^n+\sum_{j=1}^n\binom {n}{j}y^{n-j}s^j$
Let $M = max[\,\binom {n}{j}y^{n-j}\,]_{ \, 1 \le j \le n}$ so that 
$\tag 2 {(y+s)}^n \lt y^n+\sum_{j=1}^nMs^j$
We can now set $s = min(\frac{1}{2}, \frac{x - y^n}{2nM})$ so that
$\tag 3 {(y+s)}^n \lt y^n+\sum_{j=1}^nMs^j \lt y^n+\sum_{j=1}^nMs = y^n+ n M s \le y^n + \frac{x-y^n}{2} $
ensuring that ${(y+s)}^n \lt x$. $\blacksquare$
