First Question
In general, it is not true that once $k$ values of $X_n$ are specified, all values of $X_n$ are determined. Here is a simple counterexample. There are many others.
Consider the recurrence $X_{n+2}=0\cdot X_{n+1} +2X_n.$ So, in the notation of the question, $k=2$. Let us specify that $X_0=2$ and $X_2=4$. This says absolutely nothing about $X_n$ when $n$ is odd.
Since what we were asked to prove is not true, let's try to prove something near what is asked for. To make typing easier, and so that all the symbols won't get in the way of the ideas, I will mostly use a concrete example.
Look for example at $X_{n+3}=3X_{n+2}+5X_{n+1}+7X_n.\qquad\text{(Equation $1$)}$ and suppose that we know $X_m$ for three different values of $m$.
Note that if we knew $X_0$, $X_1$, and $X_2$, the first three values, then we could use Equation $1$ to calculate, one after the other, $X_n$ for all $n$.
So now suppose we know three values, but they are, say, $X_5$, $X_{22}$, and $X_{100}$.
Here is how we proceed, in principle.
The first three values are unknown. Call them $x$, $y$, and $z$. Use the recurrence to calculate the $X_n$, one after the other. Of course our answers will be in terms of the unknown $x$, $y$, and $z$. But the important thing to notice is that each $X_n$ is a simple linear combination of $x$, $y$, and $z$.
So a certain linear combination of $x$, $y$, and $z$, namely the one that gives $X_5$, has a known value. You should work out this linear combination, it can be done in two steps.
Similarly, one can in principle work out the linear combination that gives $X_{22}$, and the one that gives $X_{100}$. Now we have $3$ linear equations in the $3$ unknowns $x$, $y$, and $z$.
Solve these equations. Here we bump into a problem. Everything is OK if the matrix for the equations is invertible. However, it need not be, and then $(x, y, z)$ is not determined by $(X_5, X_{22}, X_{100})$.
However, "most of the time" the matrix will be invertible, and we will be OK. I could introduce more theory here, and mention Vandermonde determinants and their close relatives, but I doubt that you are expected to go that deep.
Consecutive values: If we know $X_m$ for $k$ consecutive values of $m$, then everything is determined. Suppose, for example, for our Equation $1$, we know $(X_{100}, X_{101}, X_{102})$. Then we can use Equation $1$ to calculate "forward", and find $X_{103}$, $X_{104}$, and so on.
But notice we can also work our way "backwards." Suppose we want $X_{99}$. Then using the fact that $X_{102}=3X_{101}+ 5X_{100}+7X_{99}$ we can solve the above equation of $X_{99}$, then do something similar to find $X_{98}$, and so on. We conclude that if $3$ consecutive values are known, everything is known.
The same idea works for general $k$. Maybe the question meant to say $k$ consecutive values, and the consecutive bit got left out!
Second Question: This one is straightforward. We want to show that putting $X_j=cp^j$ (for all $j$) "works."
Substitute $cp^j$ for $X_j$ in each side of the recurrence. We want to show that the two sides turn out to be the same: That's what it means for $X_j=cp^j$ to be a solution.
The left-hand side is $cp^{n+k} \qquad \text{(Left Side)}$ The right-hand side is messier. We get $C_{k-1}cp^{n+k-1}+C_{k-2}cp^{n+k-2}+\cdots + C_0cp^n \qquad\text{(Right side)}$
We want to show that the two displayed quantities are equal. Their difference is $cp^{n+k}-C_{k-1}cp^{n+k-1}-C_{k-2}cp^{n+k-2}-\cdots - C_0cp^n$ which is equal to $cp^n\left(p^k -C_{k-1}p^{k-1}-C_{k-2}p^{k-2}-\cdots -C_0\right)$ But the above expression is simply $cp^nf(p)$, which is $0$ since $p$ is a root of the characteristic polynomial.