I need to prove this identity using only simple arithmetics and combinatorics (or to find a counter-example): $(px+1)^{p^{k}}=(p^{k+1}x+1)$ mod $p^{k+2}$, which I verified using several values of $p$ and $k$ using GAP.
I tried the following (using Newton's binomial formula): $$(px+1)^{p^k} = \sum_{i=0}^{p^k}{p^k\choose i}p^ix^i$$ where it seems sufficient to prove that only the terms with $i \in \{0,1\}$ survive. The term for $i=2$ becomes ${p^k \choose 2} p^2x^2 = \frac{p^k(p^k-1)}{2}p^2x^2$ which disappears mod $p^{k+2}$ since $p$ is odd. The term for $i=3$ already poses a problem: ${p^k \choose 3} p^3x^3 = \frac{p^k(p^k-1)(p^k-2)}{2.3}p^3x^3$. The case where $p=3$ needs special attention but the corresponding term can be proven to disappear also. The general term ${p^k\choose i}p^ix^i$ is more of a nightmare. To delve deeper into the problem I looked at the p-adic valuation of each of the factors. Using GAP I get the following result for $\operatorname{val}_p{p^k \choose i}$ where $p=5, k=3$:
gap> List([0..5^3], i->PValuation(Binomial(5^3,i),5));
[ 0, 3, 3, 3, 3, 2, 3, 3, 3, 3, 2, 3, 3, 3, 3, 2, 3, 3, 3, 3, 2, 3, 3, 3, 3, 1, 3,
3, 3, 3, 2, 3, 3, 3, 3, 2, 3, 3, 3, 3, 2, 3, 3, 3, 3, 2, 3, 3, 3, 3, 1, 3, 3, 3,
3, 2, 3, 3, 3, 3, 2, 3, 3, 3, 3, 2, 3, 3, 3, 3, 2, 3, 3, 3, 3, 1, 3, 3, 3, 3, 2,
3, 3, 3, 3, 2, 3, 3, 3, 3, 2, 3, 3, 3, 3, 2, 3, 3, 3, 3, 1, 3, 3, 3, 3, 2, 3, 3,
3, 3, 2, 3, 3, 3, 3, 2, 3, 3, 3, 3, 2, 3, 3, 3, 3, 0 ]
From which we could hypothesise that $\operatorname{val}_p{p^k \choose i} = k$ if $\gcd(i,k) = 1$, $\operatorname{val}_p{p^k \choose i} = k-1$ if $k$ is a multiple of $p$ but not of $p^2$, ..., $\operatorname{val}_p{p^k \choose i} = k-l$ if $k$ is a multiple of $p^l$ but not of $p^{l+1}$. So proving this would solve the problem since $\operatorname{val}_p{p^i} = i$. In order to prove this hypotesis I went for an expression for $\operatorname{val}_pn!$ which I found here, resulting in $\operatorname{val}_pn! = \left \lceil{n/p}\right \rceil + \left \lceil{n/p^2}\right \rceil + \left \lceil{n/p^3}\right \rceil + \ldots$. And here I'm stuck in using this in finding the valuation of ${n \choose m} = \frac{n!}{m!(n-m)!}$.
Lemma 1: For $k>0,$ if $x\equiv y\pmod{p^k}$ then $x^p\equiv y^p\pmod{p^{k+1}}.$
Proof: If $x\equiv y\pmod {p^k}$ then $x^{p-1}+x^{p-2}y+\cdots+xy^{p-2} + y^{p-1}\equiv px^{p-1}\pmod{p^k}$ so $$x^p-y^p=(x-y)\left(x^{p-1}+x^{p-2}y+\cdots+xy^{p-2} + y^{p-1}\right)$$ is divisible by $p^{k+1}$ and hence $x^p\equiv y^{p}\pmod{p^{k+1}}.$
Lemma 2: For $i=1,\dots,p-1$, $\binom{p}{i}$ is divisible by $p.$
Proof: Left to you.
Main proof: Let $a_k=(px+1)^{p^k}$ and $b_k=p^{k+1}x+1.$ We will prove by induction that for $k\geq 0,$ $a_k\equiv b_k\pmod{p^{k+2}}.$
When $k=0$ we have that $a_0=px+1\equiv px+1=b_0\pmod{p^{2}}$ because they are equal.
Now given $$a_k\equiv b_k\pmod{p^{k+2}}$$ we need to show that $$a_{k+1}\equiv b_{k+1}\pmod{p^{k+3}}.$$ But $a_{k+1}=a_k^p,$ and lemma (1) lets us deduce that:
$$a_{k+1}=a_k^p\equiv b_k^p\pmod{p^{k+3}}$$
If we prove that:
$$b_k^{p}\equiv b_{k+1}\pmod {p^{k+3}}$$
then we are done.
Now, $$b_k^p = (p^{k+1}x+1)^p = 1+\binom{p}{1} p^{k+1}x+\sum_{i=2}^{p}\binom{p}{i}p^{i(k+1)}x^i$$
If $i=2,\dots,p-1$, we hae that $p^{1+i(k+1)}$ divides the term, and $1+i(k+1)\geq 2k+3\geq k+3.$ And when $i=p,$ we get that $p^{p(k+1)}$ divides the term, and $pk+p\geq k+3$ since $p\geq 3.$
So this means that:
$$b_k^p\equiv p^{k+2}x + 1=b_{k+1}\pmod{p^{k+3}}$$
This finishes the proof.
Your approach, trying to prove bounds on $\operatorname{val}_p\left(\binom{p^k}m\right),$ can be done.
We will show the rule that for $1\leq m\leq p^k,$:
$$\operatorname{val}_p\left(\binom{p^k}m\right)=k-\operatorname{val}_p(m)\tag{1}$$
This is due to the recursion:
$$\binom{p^k}{i +1}=\frac{p^k-i}{i+1}\binom{p^k}{i}$$
Which lets us write, for $0<m<p^k,$ that:
$$\begin{align}\operatorname{val}_p\left(\binom{p^k}m\right) &= \sum_{i=0}^{m-1}\left(\operatorname{val}_p(p^k-i) - \operatorname{val}_p(i+1)\right)\\ &=\operatorname{val}_p(p^k)-\operatorname{val}_p(m)+\sum_{i=1}^{m-1}\left(\operatorname{val}_p(p^k-i)-\operatorname{val}_p(i)\right) \end{align}$$
But, for $0<i<p^k$, $\operatorname{val}_p(p^k-i)=\operatorname{val}_p(i).$ So we have (1).
Now we have for $m>1$ that $$m-\operatorname{val}_p(m)\geq 2.\tag{2}$$
To prove this, you need to prove the inequality for $p\geq 3$ and $j\geq 1$ that: $$p^j\geq 2+j.$$
You can prove this by induction. $p^1\geq 2+1$ and $p^{j+1}\geq 2p+pj=2+2(p-1)+pj> 2+1+j.$
(1) and (2) together give you that, when $1<m\leq p^k$ then:
$$m+\operatorname{val}_p\left(\binom{p^k}m\right)=m+k-\operatorname{val}_p(m)\geq k+2$$
This shows that: $$(1+px)^{p^k}=1+\binom{p^k}{1}px+\sum_{m=2}^{p^k}\binom{p^k}{m}p^{m}x^m\equiv 1+p^{k+1}x\pmod{p^{k+2}}$$
since the terms in the sum are all divisible by $p^{k+2}.$