If you write $C_p{\bf x}=\lambda {\bf x}$, where ${\bf x}=(x_1,\dots,x_n)^T$, you get that $x_2=\lambda x_1$, $x_3=\lambda x_2$, $\dots$ , $x_n=\lambda x_{n-1}$ which means that $x_2=\lambda x_1$, $x_3=\lambda^2 x_1$, $\dots$ , $x_n=\lambda^{n-1}x_1$ and using your notation ${\bf x}=x_1v_{\lambda}$.
The answer is no in general since Hermitian matrices have real eigenvalues. So for example, there is no Hermitian matrix whose characteristic polynomial is $X^2+1$.
Even if you restrict to polynomials with real roots, I doubt you can find a simple formula : I think that if there is a rational formula that works for every polynomial with real roots, it should also apply to all polynomials. Let me explain what I mean precisely. We'll use the following lemma which states that when rational equations hold for polynomial with real roots, they should hold everywhere. Denote $\mathbb{C}_{n,u}[X]$ the set of monic complex polynomials of degree $n$.
Lemma : Let $f$ be a rational function
$$\begin{eqnarray*}f :& \mathbb{C}_{n,u} & \longrightarrow \mathbb{C}^N\\
& P &\longmapsto f(P)\end{eqnarray*}$$
such that $f$ is zero on polynomial with real roots. Then $f$ is zero.
Proof :
The map
$$\begin{eqnarray*}p_n :& \mathbb{C}^n & \longrightarrow \mathbb{C}_{n,u}[X]\\
& (\lambda_1, \ldots, \lambda_n) &\longmapsto p_n(\lambda_1, \ldots, \lambda_n) = \prod_{i = 1}^n (X-\lambda_i)\end{eqnarray*}$$
is also a rational map (meaning the coefficients of a polynomial are rational functions of its roots, and we can actually compute them, those are called elementary symmetric polynomials). By hypothesis, the function $f \circ p_n$ is zero on $\mathbb{R}^n$. But since $f \circ p_n$ is rational, it is actually zero everywhere, and because $p_n$ is surjective (every polynomial is split in $\mathbb{C}$), then $f$ is zero.
Now assume there is a rational function
$$\begin{eqnarray*}A_n :& \mathbb{C}_{n,u}[X] & \longrightarrow \mathcal{M}_n(\mathbb{C})\\
& P &\longmapsto A_n(P)\end{eqnarray*}$$
(by that I mean that the coefficients of the matrix $A_n(P)$ are rational functions of the coefficients of $P$) such that the characteristic polynomial of $A_n(P)$ is $P$ whenever $P$ has real roots. This means the rational function $P \longmapsto \det(XI_n - A_n(P)) - P$ is zero on polynomial with real roots, so it's zero everywhere, which means the characteristic polynomial of $A_n(P)$ is always $P$ without assumption on the roots of $P$.
Assume moreover that $A_n(P)$ is hermitian whenever $P$ has real roots. Then I claim $A_n(P)$ is hermitian for any real polynomial $P$ from the same kind of argument. Indeed denote $A_n^* : P \longmapsto \left[A_n(P^*)\right]^*$, where $P^*$ denotes the complex conjugate of the polynomial $P$, and $\left[A_n(P^*)\right]^*$ is the conjugate transpose of the matrix $A_n(P^*)$. This is a rational function (beware that $P \mapsto [A_n(P)]^*$ is not rational however !). Our assumption is that the rational function $A_n - A_n^*$ is zero on all polynomial with real roots, so it's zero everywhere. When $P$ is real, this means $A_n(P)$ is hermitian (because $A_n(P) = A_n^*(P) = [A_n(P)]^*$, the last equality being only true when $P$ is real). This yields a contradiction if $P$ is a real polynomial with complex roots.
Best Answer
Yes, this $P$ is unique. We can see that this holds as follows. First, suppose that $P = P_1$ and $P=P_2$ satisfy the required conditions; our goal is to show that $P_1 = P_2$. We note that $$ A = P_1 \mathbf A P_1^{-1} = P_2 \mathbf A P_2^{-1} \implies \mathbf A = (P_1^{-1}P_2) \mathbf A (P_1^{-1}P_2)^{-1}\\ b = P_1e_n = P_2 e_n \implies P_1^{-1}P_2 e_n = e_n. $$ Let $Q = P_1P_2^{-1}$; we want to use the above to show that $Q = I$ (the identity matrix) and thereby conclude that $P_1 = P_2$. Note the following:
This claim is proved, for instance, in Matrix Analysis by Horn and Johnson. We note that $$ \mathbf A = Q \mathbf A Q^{-1} \implies \mathbf A Q = Q \mathbf A. $$ By Claim 1, there exists a polynomial $f$ for which $Q = f(\mathbf A)$. Moreover, we have $$ Qe_n = e_n \implies (Q - I)e_n = 0 \implies (f(\mathbf A) - I)e_n = 0. $$
By the Cayley-Hamilton theorem, we can write $f(\mathbf A) - I$ as $g(\mathbf A)$ for some polynomial $g$ with degree at most $n-1$. Let $g(x) = c_0 + c_1 x + \cdots + c_{n-1}x^{n-1}$. We note that $$ g(\mathbf A) e_n = 0 \implies c_0 e_1 + c_1 \mathbf A e_n + \cdots + c_{n-1} \mathbf A^{n-1}e_n = 0 \implies\\ \pmatrix{e_n & \mathbf A e_n & \cdots & \mathbf A^{n-1} e_n} \pmatrix{c_0\\ c_1 \\ \vdots \\ c_{n-1}} = 0. $$ By Claim 2, $\pmatrix{e_n & \mathbf A e_n & \cdots & \mathbf A^{n-1}e_n}$ has full rank. Thus, we can conclude from the above that $c_0 = c_1 = \cdots = c_{n-1} = 0$. That is, we have $$ g(\mathbf A) = f(\mathbf A) - I = 0. $$ That is, $Q = f(\mathbf A) = I$, which is what we wanted to show.