What is the relation between 'the order of $x^k = n/{\gcd(k,n)}$' and Lagrange's Theorem?

To answer your question directly w.r.t. the direction Artin takes regarding order and Lagrange.

Well Prop.2.4.2 sets up cyclic groups, so we know, for some element $x$ in a group $G$, that taking powers of $x$ generates a cyclic subgroup of $G$, and that it is of order $n$:
$$\langle x\rangle=\{1,x,x^2,\dotsc,x^{n-1}\}\le G$$ We can say no more at this point about the relationship between $|\langle x\rangle|$ and $|G|$.

Let $x$ be an element of order $n$. Then the next proposition from Artin gives the recipe for the order of an arbitrary power of $x$, say $x^k$:

Proposition 2.4.3

Let $x$ be an element of finite order $n$ in a group $G$, and $k,q,r\in\mathbb{Z}$ s.t. $k=nq+r$, $0\le r<n$. Now

$(1)$ $x^k=x^r$

$(2)$ $x^k=1$ iff $r=0$

$(3)$ Let $d=\gcd(k,n)$. Then $\operatorname{ord}(x^k)=n/d$

Now lets see where we are immediately after Prop.2.4.3. A particular case of $(3)$ of Prop.2.4.3 in the case that $n$ is prime is immediate, even though Artin does not explicitly state it here as a corollary. For convenience let us define it as $(3a)$:

$(3a)$ Let $n=p$ be a prime. Then for $k=pq+r$, $1\le r<p$, $\gcd(k,p)=1$. Then $\operatorname{ord}(x^k)=p/1=p$

So let's see what Prop.2.4.3 gets us with this particular case of having $n=p$, i.e., when our element $x$ has the order of a prime $p$.

Well $(2)$ tells us the only power of $x$ that gives the identity is $x^0=1$, so for the set of powers $$X=\{x^0,x^1,x^2,\dotsc,x^{p-1}\}$$ we know none of $x^1$, $x^2,\dotsc,x^{p-1}$ equal $1$.

The next question is then what of the orders of $x^1$, $x^2,\dotsc,x^{p-1}$? Well $(3)$ tells us this: we know, for $1\le k\le p-1$, that $\gcd(k,p)=1$. This then gives the order of each nonidentity element $x^k$ as $\operatorname{ord}(x^k)=p/\gcd(k,p)=p/1=p$, and so each of the $p-1$ number of nonidentity elements $x^k$ generate a cyclic subgroup of order $p$, $$\langle x^k\rangle\le G$$

Now Prop.2.4.3 does not mention the actual relationship between the order of the group $G$ and the cyclic subgroups of order $p$ formed by the $p-1$ nonidentity elements of order $p$, just that they exist within it.

Upto this point Artin has not mentioned homomorphisms, isomorphisms, equivalence relations or partitions.

Now in section 2.2 Artin defines the order of a group $G$ as $$|G|=\text{ the number of elements $G$ contains.}$$ So for us $|G|=p$. Again Artin has not mentioned isomorphisms by Prop.2.4.3 so we can't talk of isomorphism classes, but again that is not what is needed for Corollary 2.8.11.

Now we must ask: can Corollary 2.8.11 be a corollary to Prop.2.4.3? Let's look at it:

Corollary 2.8.11 Suppose that $G$ has prime order $p$. Let $a\neq1$. Then $G$ is the cyclic group $\langle a\rangle$ generated by $a$.

Artin proves this by Lagrange; he states if $a\neq1$, then, by Lagrange, its order divides $|G|=p$ and so must be of order $p$ itself, since $p$ is prime, and so its cyclic subgroup generates $G$. QED.

We are coming from the other angle using what we know from Prop.2.4.3. Well we know about order, this means the number of elements in a group. We are told $G$ has order $p$, so now the question is: if $G$ has order $p$ does this mean that every nonidentity element $a$ in $G$ also has order $p$, which would then imply, without mentioning isomorphism as such, that $\langle a\rangle=G$? Remember Prop.2.4.3 only works if we know the order of the element in question, and thus far this could be anything in relation to $G$. We can't use division as Artin does as this uses Lagrange.

But what we do know is all about cyclic groups. So now we work backwards. Consider $G$, it has $p$ elements, $$G=\{a_1,a_2,\dotsc,a_p\}$$ Now let $a_1=1$, which, since $G$ is a group, the identity is unique and so no other elements are $1$. So what of the $p-1$ elements $a_2,\dotsc,a_p$? We know, by Section 2.4, that each element forms a cyclic subgroup of $G$ with order equal to the smallest integer s.t. $a_i^n=1$. So take some arbitrary nonidentity element $x$ in $G$ and consider its order $n$, with the powers of $x$ given in the set, $$X=\{x^1,x^2,\dotsc,x^{n-1},x^n=1\}$$ All we can say at the moment is that $n\leq p$. If we can deduce $n=p$ then from Prop.2.4.3 it quickly follows all nonidentity elements $a$ have order $p$, since $a$ was an arbitrary nonidentity element, and this in turn implies $\langle a\rangle=G$ since both have $p$ distinct elements, easy enough to set up a bijection here.

Now Prop.2.4.3 $(1)$ states $x^k=x^r$. So let $k=nq+r$, which by virtue of the cyclic group regenerating itself cyclically, we can take $q=0$, $1$, $2,\dotsc$, etc., to give $k=r$, $k=n+r$, $k=2n+r,\dotsc$, and so on. This generates sets of powers, each of size $n$ thus: \begin{align*} \langle x\rangle&=\{x^1,x^2,\dotsc,x^n=1\}=\{x^{n+1},x^{n+2},\dotsc,x^{2n}=1\}\\ &=\{x^{2n+1},x^{2n+2},\dotsc,x^{3n}=1\} =\dots\{x^{(j-1)n+1},x^{(j-1)n+2},\dotsc,x^{jn}=1\}=\dots\tag{1} \end{align*}

To complete the proof we look at the order of $G$ in relation to the order of the cyclic group and the repeating sets in $(1)$. Since there are $p$ elements in $G$ take an arbitrary nonidentity element $y$, then we know $y^0=y^{p}=1$, since $0\equiv p\pmod{p}$, that is the powers in the set $$Y=\{y^1,y^2,\dotsc,y^{p-1},y^p=y^0=1\}$$ cycle after every $p$th power is taken. Now the powers in $Y$ need not be distinct, so let us look at the sets in $(1)$ and assume that $n<p$. Then say it takes $j$ sets of $n$ elements to cycle through $p$ amount of elements: Note these sets only cycle through the $n$ elements in the subgroup $\langle x\rangle$ repeatedly, and not the whole of $G$, since we have assumed $n<p$. This means $jn=p$. If not, then we should have $x^p\neq1$, which implies $x^0=x^k$ for some $1\leq k< n$. But this contradicts the uniqueness of the identity, so $jn=p$ has to have $n=p$, $j=1$ and $\langle x\rangle=G$.

Therefore technically Prop.2.4.3 $(3a)$ only works if we know the order of a nonidentity element is $p$, but what we have to do first is consider the structure of the cyclic group itself, since we cannot assume that just because a group $G$ has order $p$ that any element in it actually has order $p$.

So to finish Prop.2.4.3 isn't enough on its own to imply Cor.2.11.8. Something like I have said above has to be explained first, and only then can we have Cor.2.11.8 as an actual corollary to Prop.2.4.3.

To quickly address the converse: whether Cor.2.8.11 implies $3$rd bullet of Prop.2.4.3 in the case that $n$ is prime. Cor.2.8.11 tells us every element $x\neq1$ of a group of order $p$ also has order $p$, and so they all generate $G$. We already know the order of $x^k$, for $k\ne p$, is equal to $p$ from Cor.2.11.8, and that this satisfies a particular case of the $3$rd bullet of Prop.2.4.3.

We can certainly note $\gcd(k,p)=1$, for $k\ne p$, and that the order of $x^k$ is $p$ by Cor.2.11.8, since these are precisely the nonidentity elements mentioned in Cor.2.11.8. So we can write the $3$rd bullet point in the case $|G|=p$, in the form $p/\gcd(k,p)=p$, but it doesn't imply, on its own, the actual $3$rd bullet point

Let $d$ be the greatest common divisor of $k$ and $n$. The order of $x^k$ is equal to $n/d$

so it would be more like just an observation at this stage.

Let $x$ be an element of finite order $n$ in a group, and $k,q,r\in\mathbb{Z}$ s.t. $k=nq+r$, $0\le r<n$. Now Prop.2.4.3 from Artin gives, (with $(4)$ added on)

$(1)$ $x^k=x^r$

$(2)$ $x^k=1$ iff $r=0$

$(3)$ Let $d=\gcd(k,n)$. Then $\operatorname{ord}(x^k)=n/d$

$(4)$ Let $n=p$ be a prime. Then for $k=pq+r$, $1\le r<p$, $\gcd(k,p)=1$. Then $\operatorname{ord}(x^k)=p/1=p$

Let $G$ be a group containing $p$ elements, where $p$ is a prime. Now consider the set $$S=\{0,1,2,\dotsc,p-1\}$$ These are $p$ numbers that are pairwise incongruent modulo $p$, and so form a complete set of residues modulo $p$. Equivalently each number in $S$ belongs to a different equivalence class, and since there are $p$ of them, with $p$ prime, then if $a$ and $b$ are in $S$ and we have $a\equiv b\pmod{p}$ this means $a=b$, i.e. they are both in the same residue class, and so for the rest.

Now for $a$, $b\in S$, we shall use addition of the integers modulo $p$ as our elements. So modulo $5$, $x$ can be one of $0$, $1$, $2$, $3$, $4$. Group composition is given by $+$ with the result taken modulo $p$, so if $x=3$, $x^2=3+3\equiv1\pmod{5}$, or in general $x^a=ax=\underbrace{x+\dotsb+x}_{\text{$a$ times}}$. Now $a\equiv b\pmod{p}$ implies $a=b$. (At this point all we can say is $x^0=x^0$, $x^1=x^1$, $x^2=x^2,\dotsc,x^{p-1}=x^{p-1}$.)

The problem now is that we cannot immediately say that if $a\not\equiv b\pmod{p}$ then $x^a\neq x^b$. So assume this does hold for some $a$, $b\in S$ and derive a contradiction. WLOG, let $0\le b<a<p$, where $a-b=c\in S$ also with $c\neq0$. Let $x$ be a nonidentity element. We can write $x^a$ and $x^b$ as multiples in the congruence thus: $ax\equiv bx\pmod{p}$, and so $ax-bx=(a-b)x\equiv cx\equiv0\pmod{p}$. Now $a$, $b$, $c\in S$, with only $b$ having the possibility of being zero, since we took $a>b$. But since $x\neq0$ we must have $c=0$ and $a=b$, contrary to what was assumed.

Hence if $a\not\equiv b\pmod{p}$ then $x^a\neq x^b$, and so the powers in the set $$X=\{x^0,\ x^1,\ x^2,\dotsc,x^{p-1}\}$$ are all distinct from each other.

Since the number of distinct elements in $G$ is $p$, this gives us $p-1$ nonidentity elements $x_i$ all forming sets of $p$ distinct elements, as in the set $X$, thus, $$X_i=\{x_i^0,x_i^1,x_i^2,\dotsc,x_i^{p-1}\},\quad 1\le i\le p-1$$

Let $y$ be some nonidentity element of $G$. Consider the cyclic subgroup $\langle y^c\rangle$, where $c$ is some number in the range $0<c\le p-1$. The multiples of $c$ are taken modulo $p$ to ensure a bijection with $S$, which then implies the set of elements thus formed in $\langle y^c\rangle$ can be put into a bijection with $X$.

Hence $\langle y^c\rangle$ and the whole group $G$ exhaust all elements and we have $$\langle y^c\rangle\cong G$$ Hence we have $p-1$ cyclic subgroups, $\langle y^c\rangle$, generating $G$.