(Remarks, than a "real" answer): The first theorem is a kind of precise generalization of the Theorem of Cauchy ( that there is an element of prime order $p$ in the finite group $G$ when $|G|$ is divisible by $p$). Frobenius's theorem does imply Cauchy's theorem, and therefore Sylow's theorem. However, one has to take care to avoid circularity. Most published proofs of Frobenius's theorem of which I am aware assume Cauchy's theorem, at least implicitly, but this can be avoided with care. To be precise, a counterexample to Frobenius's theorem with first $|G|$, then $n$ minimal, would reduce to the case that $n$ is prime and $|Z(G)|$ is divisible by $n$. Hence a unified proof of Frobenius's theorem and Cauchy's theorem can be given. Also a unified proof of Cauchy's theorem and Sylow's theorem can be given. Hence Frobenius's theorem, Cauchy's theorem and Sylow's theorem can all be seen as part of the same circle of ideas. The fact that if there are just $n$ solutions (and $n$ divides $|G|$), then they form a subgroup has a satisfactory ring to it, and is a natural question. However, I do not know any immediate applications of this fact myself.

MUCH later edit: I might add that if it were possible to prove this conjecture of Frobenius ( that if there are just $n$ solutions for $n$ a divisor of the order of $G,$ then they form a subgroup), and it could be done without using characters, then it would provide a character free proof of the other famous theorem of Frobenius ( that if each non-identity element of a finite transitive permutation group fixes at most one point, then the elements which do not fix a unique point form a subgroup). There is still no completely character free proof of that theorem, though Terry Tao has a proof which essentially reduces it to a question about characters of finite Abelian groups.

The reason that the conjecture implies the (known) theorem is that if $G$ is the permutation group, and $H$ is a point stabilizer, then $ H \cap H^{g} = 1$ for all $g \in G \backslash H$. Hence there are $[G:H](|H|-1)$ non-identity elements which fix a unique point, and $[G:H]$ elements which do not fix a unique point. Set $n = [G:H].$ Then $n$ is relatively prime to $|H|$ since $[G:H] \equiv 1$ (mod $|H|$), since, eg, the double coset $HgH$ contains $|H|^{2}$ elements for any $g \in G \backslash H.$ Since every element which fixes a unique point is in a conjugate of $H,$ no such element has order dividing $n,$ and $G$ contains exactly $n$ solutions of $x^{n} = 1.$

Later edit: In view of the answers by K.Conrad and J. Moller, I will outline a proof that in the special case that $n= |G|_{p}$ for a prime $p,$ Frobenius's theorem admits a fairly direct inductive proof. This proof is related to, but slightly different from, the proof that appears in the AMM paper that Marty Isaacs and I wrote- the proof bypasses the need to assume Cauchy's Theorem, though in some ways it is more sophisticated : We proceed by induction on $|G|,$ and we are trying to prove that the number of $p$-elements of $G$ (including the identity as a $p$-element) is divisible by $|G|_{p}.$ Suppose first that there is an element $y \neq 1$ of order prime to $p$ with $y \in Z(G).$ We note that there is a bijection between $p$-elements of $G$ and $p$-elements of $G/Y$ where $Y = \langle y \rangle.$ Clearly, the image of a $p$-element of $G$ in $G/Y$ is still a $p$-element. On the other hand, given any $x \in G$ such that $xY$ is a $p$-element in $G/Y,$ we see that $xy^{j}$ is a $p$-element for some value of $j$ with $0 \leq j < |Y|.$ This value of $j$ is unique, since otherwise $y^{k}$ is a $p$-element for some $k$ with $0 < k < |Y|,$ which is not the case. Since we are only interested in the coset $xY,$ we might as well suppose that $x$ itself is a $p$-element. What we have really proved that given a coset $xY$ in $G/Y$ which is a $p$-element, there is a unique coset representative which is a $p$-element. By induction, the number of $p$-elements of $G/Y$ is a multiple of $[G:Y]_{p} = |G|_{p}.$ Hence we may suppose that there is no such central non-identity element $y$ of order prime to $p.$

Now given any element $x \in G$ which is not a $p$-element, we may (uniquely) write $x = yz = zy$ where $y \neq 1$ is an element of order prime to $p$ and $z$ is a $p$-element of $C_{G}(y).$ For any given element $y$ of order prime to $p,$ the number of choices of of $z$ is the number of $p$-elements of $C_{G}(y)$ which, by induction is divisible by $|C_{G}(y)|_{p}$ as $y \not \in Z(G).$ If we count the contribution from the conjugacy class of $y,$ we get a multiple of $[G:C_{G}(y)]|C_{G}(y)|_{p},$ so certainly a multiple of $|G|_{p}.$ Doing this for every conjugacy class of non-identity elements of order prime to $p,$ we see that the number of elements of $G$ which are NOT $p$-elements is divisible by $|G|_{p}.$ Since $|G|$ is certainly divisible by $|G|_{p},$ we see that the number of $p$-elements of $G$ is an integer multiple of $|G|_{p}.$