Not a truly satisfying answer, but maybe it puts things under a slightly more natural view. Consider the linear map $L$ on the space $k[x]$ such that $Lp(x):=p(x^2)$ . So $(L-I)^k$ expands by the binomial theorem, and $f_k=(L-I)^kf_0$ .

*edit I*. And, of course $(L-I)[1]=0$ , whence the form of your polynomials. That said, I'm sorry that I have no idea either, of where these polynomials may appear in mathematics.

**A possible source.** Let $S$ be the shift operator on sequences, and let $M$ be the sequence $M(k):=x^{2^k}$, for a given $x$. Then $f_n(x)$ is also equal to $[(S-I)^n M](0)$, the $n$-th finite difference at $k=0$ of the sequence $M$. Let in particular $x\ge 1$. I would like to believe that there is a measure $\mu_x$ that solves the Stieltjes moment problem on $[0,\infty)$ wrto the sequence of weights $M$, that is $$x^{2^n}=\int_0^\infty t^n d\mu_x(t)\, ,$$

so that the $p_k$ would have a representation by the kernel $\{\mu_x\}_{x\ge1}$ $$p_k(x)=\int_0^\infty (t-1)^n d\mu_x(t).$$

*edit II.* I've made some experiment by Maple to see if the compatibility condition (see the link) is fulfilled, that is, the non-negativity of $\Delta_n(x):=\operatorname{det}\Big(x^{2^{i+j}}\Big)_{0\le i < n \atop 0\le j< n} $ and of $\Delta_n(x^2)$. In fact for $n\le 5$ it is true that $\Delta_n(x)>0$ for all $x> 1$, as it follows from the factorizations:

$$\Delta_1(x)=x;$$
$$\Delta_2(x)=x^4(x-1);$$
$$\Delta_3(x)=x^{12}(x^2-1)(x^3-1)(x^4-1) (x^3+x+1) ;$$
$$\Delta_4(x)=x^{32}(x-1)(x^2-1)(x^3-1)(x^4-1)(x^6-1)(x^7-1)\,$$ $$ (1+x+2\,{x}^{2}+3\,{x}^{3}+2\,{x}^{4}+3\,{x}^{5}+4\,{x}^{6}+4\,{x}^{7}
+4\,{x}^{8}+6\,{x}^{9}+5\,{x}^{10}+4\,{x}^{11}+5\,{x}^{12}+4\,{x}^{13}
+4\,{x}^{14}+4\,{x}^{15}+5\,{x}^{16}+3\,{x}^{17}+3\,{x}^{18}+2\,{x}^{
19}+3\,{x}^{20}+2\,{x}^{21}+2\,{x}^{22}+2{x}^{23}+2\,{x}^{24}+{x}^{
26}+{x}^{27}+{x}^{28}+{x}^{30});$$
$$\Delta_5(x)=x^{80}(x^2-1) (x^3-1) (x^4-1) (x^5-1)(x^6-1) (x^7-1)(x^8-1)(x^9-1)(x^{12}-1)$$ $$(x^{14}-1) (x^8-x^7 + x^5 -x^4 +x^3 -x +1) P(x)$$
and $P(x)$ is a $183$-degree polynomial with non-negative integer coefficients.