Solution:
Note that by criterion for divisibility by $11$ and the definition of a palindrome we have that every palindrome that has even number of digits is divisible by $11$.
Since $11^{5} = 161051$ is not a palindrome and since $11$ cannot divide $p^{k}$ for any prime other than $11$ we are now left to prove that no prime whose all powers have odd number of digits exists.

Assume the contrary. It means that the difference between the numbers of digits of $p^{m}$ and $p^{m+1}$ is even number. We will prove that for every natural $m$, the difference is the same even number.
If we assume not, that means that the difference for some $m_{1}$ has at least $2$ digits more than the difference for some $m_{2}$. We will prove that this is impossible.
Let $p^{m_{1}} = 10^{t_{1}} \cdot a_{1}$, $p^{m_{2}} = 10^{t_{2}} \cdot a_{2}$ and $p = 10^{h} \cdot z$, where
$$1 < a_{1}, a_{2}, z < 10$$
This implies that
$$1 < a_{1} \cdot z,\ a_{2} \cdot z < 100$$
which further implies that multiplying these powers of $p$ by $p$ can increase their number of digits by either $h$ or $h+1$.
This is a contradiction. Call the difference between numbers of digits of consecutive powers $d$. Number $p$ clearly cannot be equal to $10^{d}$ for $d \geq 1$ because $10$ is divisible by two primes, but for $d=0$, we would have that $1$ is a prime which is not true.

Case 1. $p > 10^{d}$. Let $p = 10^{d} \cdot a$, for some real number $a$ greater than $1$. (1)
From the definition of $d$ we also see that $a$ is smaller than $10$. (2)
From (1) we see that powering $a$ gives us arbitrarily large numbers and from (2) we conclude that there is some natural power of $a$, call it $b$, greater than $1$, such that
$$10 < a^{b} < 100$$
It is clear that $p^{b}$ has exactly $(b-1)d+1$ digits more than $p$ has, which is an odd number, but sum of even numbers is even.

Case 2. $p < 10^{d}$. Let $p = \frac{10^{d}}{a}$, for some real number $a$ greater than $1$. (1) From the definition of $d$ we also see that $a$ is smaller than $10$. (2)
From (1) we see that powering $a$ gives us arbitrarily large numbers and from (2) we conclude that there is some natural power of $a$, call it $b$, greater than $1$, such that
$$10 < a^{b} < 100$$
It is clear that $p^{b}$ has exactly $(b-1)d-1$ digits more than $p$ has, which is an odd number, but sum of even numbers is even.

We have now arrived at the desired contradiction for both cases and have thus finished the proof.

Solution:
Note that the sequence $\{p^{n}\}$ is periodic $(\bmod\ 10)$. Let the period be $d$. Also, let $p^{d} = g$.
Since all powers of $p$ are palindromes, all powers of $g$ are as well. Since $\{g^{n}\}$ is constant (mod $10$), the leftmost digit of each power of $g$ is equal to some $f$.
We will prove that the difference between numbers of digits of $g^{m}$ and $g^{m+1}$ is equal to some $r$ for every natural number $m$.
This is true due to size reasons. Namely, to add exactly $k$ digits, and yet to have the same leftmost digit, we need to multiply the number by at least $5 \cdot 10^{k-1}$ (if $k=0$ then it's $1$) and by at most $2 \cdot 10^{k}$ (values depend on the leftmost digit, it can easily be seen that leftmost digit being $1$ yields the extremal values). Notice that
$$2 \cdot 10^{k} < 5 \cdot 10^{k+1-1}$$
Since this inequality has clearly shown that the interval of multipliers which add exactly $k$ digits and leave the leftmost digit the same is disjunct from the same kind of interval for $k+1$ digits, which implies that no number can belong to both intervals, we have successfully proven the claim.
Clearly, $g$ cannot be equal to $10^{r}$ for $r \geq 1$ because a palindrome cannot be divisible by $10$, but for $r=0$ we again cannot have the equality because $1$ is not a natural power of a prime.

Case 1. $g > 10^{r}$. Let $g = 10^{r} \cdot a$, where $a$ is a real number, $10 > a > 1$. (1) Here, $a$ is less than $10$ because if it was not, multiplying by $g$ would add at least $r+1$ digits, which is impossible.
From (1) we see that powering $a$ gives us arbitrarily large numbers and that there is some natural power of $a$, call it $b$, greater than $1$, such that
$$10 < a^{b} < 100$$
Pick smallest such $b$.
Now we easily see that the difference between numbers of digits of numbers $g^{b-1}$ and $g^{b}$ is exactly $r+1$.

Case 2. $g < 10^{r}$. Let $g = \frac{10^{r}}{a}$, where $a$ is a real number, $10 > a > 1$. (2) Here, $a$ is less than $10$ because if it was not, multiplying by $g$ would add at most $r-1$ digits, which is impossible.
From (2) we see that powering $a$ gives us arbitrarily large numbers and that there is some natural power of $a$, call it $b$, greater than $1$, such that
$$10 < a^{b} < 100$$
Pick smallest such $b$.
Now we easily see that the difference between numbers of digits of numbers $g^{b-1}$ and $g^{b}$ is exactly $r-1$.

We have arrived at the desired contradiction for both cases and have thus finished the proof.