Theorem: Let $M$ be an $n \times n$ matrix over a field $F$ and fix $1 \le i, j \le n$. Suppose that over $\bar{F}$ the characteristic polynomial of $M$ has roots $\lambda_1, ... \lambda_m$ with multiplicities $e_1, ... e_m$. Then we can write $(M^n)_{ij} = \sum_{k=1}^m p_k(n) \lambda_k^n$
where $p_i$ is a polynomial of degree at most one less than the largest size of a Jordan block of $M$ with eigenvalue $\lambda_i$. This follows from the theory of Jordan normal form.
In this case $M$ is a circulant matrix so one can write down its eigenvalues fairly explicitly using the discrete Fourier transform (equivalently, using the representation theory of a finite cyclic group): they are given by $\lambda_k = \zeta_p^k (1 + \zeta_p^{-1})$
where $\zeta_p$ is a primitive $p^{th}$ root of unity over $\mathbb{F}_2$. The polynomial $x^p - 1$ is separable over $\mathbb{F}_2$, so the $\lambda_k$ are distinct and the polynomials $p_k(n)$ are constant.
Now, $1 + \zeta_p^{-1}$ has conjugates $1 + \zeta_p^{-1}, 1 + \zeta_p^{-2}, 1 + \zeta_p^{-2^2}, 1 + \zeta_p^{-2^3}, ...$
by repeatedly applying the Frobenius map. This sequence starts repeating precisely at the smallest $r$ such that $2^r \equiv 1 \bmod p$, so in other words $1 + \zeta_p^{-1}$ lives in $\mathbb{F}_{2^r}$ where $r$ is the order of $2 \bmod p$ and hence has multiplicative order dividing $\boxed{2^r - 1}$. Since $p | 2^r - 1$ by assumption, each $\lambda_k$ has this period also.
You can determine a closed form in one of various ways. My preferred general method is to write down the matrix generating function $(I - tM)^{-1} = \sum_{n \ge 0} M^n t^n$
and isolate its entries using Cramer's rule. In this particular case it is fairly straightforward to write your initial vector as a linear combination of the eigenvectors of $M$. These eigenvectors are $u_{ij} = \frac{1}{p} \zeta_p^{ij}$
where $u_k$ has eigenvalue $\lambda_k$ (representation theory of cyclic groups!), and we have $v_0 = \frac{1}{p} \sum_{k=0}^{p-1} u_k$
hence $v_n = \frac{1}{p} \sum_{k=0}^{p-1} \zeta_p^{nk} (1 + \zeta_p^{-1})^n u_k.$