Is there an analytic solution for such problem? Given function $$f_n(x) = \cos x - (\cos \cos x) + (\cos \cos \cos x) - (\cos \cos \cos \cos x) + \dots + (-1)^{n-1} \underbrace{ \cos \cos \dots \cos }_n x,$$
where $n \in \mathbb{N}$ and $\underbrace{ \cos \cos \dots \cos }_n$ means cosine of cosine of cosine and so on $n$ times, find value of 
$$\sup_{n \rightarrow \infty, x \in \mathbb{R}} \{f_n(x)\}^{n}_{k=1}$$

This is not a full answer, but should help you to derive bounds for the value in both directions.
Split the sum
$$ \sum_{n=1}^\infty (-1)^{n-1} \cos^n(x) $$
into a finite part of leading terms with odd length and the remaining higher terms
$$ \sum_{n=1}^\infty (-1)^{n-1} \cos^n(x) 
= \sum_{n=1}^{2N +1} (-1)^{n-1} \cos^n(x) + \sum_{n=2N+2}^\infty (-1)^{n-1} \cos^n(x). $$
The maximum of the first part ($f_{2N+1}$) is at $x=0$ and can be bounded in both directions. The supremum of the sequence is thus also attained at (or rather in a neighborhood of)  $x=0$. This follows from the following approximation for the remaining terms (or more precisely, from a concrete bound that should be obtainaned from it).
For the remaining terms, observe that the sequence $\cos^n(x)$ converges to a unique fixpoint for all $x \in \mathbb{R}$, the unique solution $x_0$ of $\cos x = x$. The summands are thus almost equal up to their alternating signs. We "transform coordinates" and instead work with the summands $\pm \cos^n(x) - x_0$.
Let $r = |(\frac{d}{dx} \cos)(x_0)| = |\sin(x_0)|$.
Then $r$ is the convergence order of $\cos^n(x) \to x_0$, i. e.
$$ \Delta_n := |\cos^n(x) - x_0| \approx \Delta_0 r^n. $$
(This follows by a first-order Taylor approximation of the recurrence equation around $x_0$.)
For the remaining terms we thus get approximately
\begin{align*}
 &\sum_{n = N + 1}^\infty (\Delta_{2n} - \Delta_{2n+1}) \\
= &\sum_{n = N + 1}^\infty (1-r) \Delta_{2n} \\
= &(1-r) \Delta_{2N + 2} \sum{n = 0}^\infty r^2 \\
= &\Delta_{2N+2} \frac{1-r}{1-r^2} \\
= &\Delta_{2N+2} \frac{1}{1+r}.
\end{align*}
Concerning the question of an analytic form and whether the value is expressible in terms of $\pi$ I am inclined to say no to both.
According to a calculation with Sage with 2000 bits of precision, the value has long since stabilized at $f_{10001}$ and differs from $\pi/2$ by about 3.9e-5.
Already the solution of $\cos(x) - x=0$ should be transcendental and not expressible in the standard transcendental functions, but such proofs are in general incredibly difficult.
