I am supposed to rewrite Rodrigues' rotation formula
$R(v)=v\cos \phi+k(k\cdot v)(1-\cos\phi)+(k\times v)\sin\phi$
in the form of spectral decomposition. I can figure out that the eigenvalues are 1, $e^{i\phi}$, $e^{-i\phi}$ and the eigenvector belonging to 1 is k, so we have
$R=kk^T+e^{i\phi}v_+v_+^T+e^{-i\phi}v_-v_-^T$ ,
but I'm not sure how to find the other eigenvectors $v_\pm$ without explicitly calculating $\mathrm{Ker}(R-\lambda I)$ from the matrix form. Is there a more elegant, painless way how to solve this? Or maybe I should choose a different approach altogether? Thanks for any help.
Rodrigues' rotation formula is completely irrelevant to this problem. It is simply a clever way of writing down the action of the operator $R(\phi,k)$, which I will use to denote rotation by angle $\phi$ about axis $k$. Given that's the case, all you're really doing is writing down the spectral decomposition of a rotation matrix.
Since $k$ is the axis, it also serves as one of the eigenvectors. Let $u_1$ and $u_2$ denote any orthonormal basis for the plane orthogonal to $k$, oriented so that $u_1 \times u_2 = k$, i.e., such that $R(\pi/2,k)u_1 = u_2$ and $R(\pi/2,k)u_2 = -u_1$. Then the other two eigenvectors are $$v_{\pm} = (u_1 \pm iu_2)/\sqrt{2}.$$ All of this just follows from the familiar spectral decomposition of the rotation matrix $$R(\phi) = \begin{pmatrix}\cos\phi & -\sin\phi \\ \sin\phi & \cos\phi\end{pmatrix}.$$
Edit: It might be instructive to see how this spectral decomposition is related to the Rodrigues' formula itself. Let $$R = kk^\dagger + e^{i\phi}v_+v_+^\dagger + e^{-i\phi}v_{-}v_{-}^\dagger$$ be the spectral decomposition as outlined above. I use daggers to indicate Hermitian conjugation. Let me expand everything out in terms of sines, cosines, and the orthonormal basis $\{k,u_1,u_2\}$. Doing so, we get $$R = kk^\dagger + (u_1u_1^\dagger + u_2u_2^\dagger)\cos\phi + (u_1u_2^\dagger - u_2u_1^\dagger)\sin\phi.$$ Matching the individual terms to Rodrigues' formula, we see that the $kk^\dagger$ term is responsible for $k(k\cdot v)$ through the action $$kk^\dagger v = k(k\cdot v).$$ The $(u_1u_1^\dagger + u_2u_2^\dagger)\cos\phi$ is responsible for the $(v - k(k\cdot v))\cos\phi$ term through the resolution of the identity: $$kk^\dagger + u_1u_1^\dagger + u_2u_2^\dagger = I.$$ Through this we get $$(u_1u_1^\dagger + u_2u_2^\dagger)v\cos\phi = (I - kk^\dagger)v\cos\phi = (v - k(k\cdot v))\cos\phi.$$ The final term $(u_1u_2^\dagger - u_2u_1^\dagger)\sin\phi$ is responsible for the $(k\times v)\sin\phi$. This is a bit trickier to show, and it amounts to showing that the matrix $[k]_\times\equiv u_1u_2^\dagger - u_2u_1^\dagger$ is a representation of the cross-product, i.e., for any vector $v$, we have $[k]_\times v = k\times v$.
You can verify this through a direct basis calculation. Alternatively, if you know a little bit about the representation theory of $SO(3)$, you can use the fact that the action of the cross-product is the infinitesimal generator of rotations (i.e., the adjoint representation of $\mathfrak{so}(3)$). Through this, we get $$\frac{d}{d\phi}\bigg|_{\phi=0}R(\phi,k) = [k]_\times.$$ Using our spectral resolution, this is $$\frac{d}{d\phi}\bigg|_{\phi=0}R(\phi,k) = i(v_+v_+^\dagger - v_{-}v_{-}^\dagger) = u_1u_2^\dagger - u_2u_1^\dagger.$$ Putting all of this together, we get the final term as $$(u_1u_2^\dagger - u_2u_1^\dagger)v\sin\phi = [k]_\times v\sin\phi = (k\times v)\sin\phi.$$ This gives you the precise relation of the spectral resolution to the Rodrigues' formula.
Edit 2: To see that the other two eigenvectors are $v_{\pm}$ given by $(u_1\pm iu_2)/\sqrt{2}$, it suffices to work in a basis (the $\sqrt{2}$s are just so the vectors are normalized). Since we know one of our eigenvectors is $k$, so let's pick the ordered orthonormal basis $\{u_1,u_2,k\}$, where $u_1$ and $u_2$ are defined and oriented as before.
In this basis, the rotation matrix is given by $$R(\phi,k) = \begin{pmatrix}\cos\phi & -\sin\phi & 0\\ \sin\phi & \cos\phi & 0 \\ 0 & 0 & 1\end{pmatrix}.$$ A quick calculation shows you that the remaining eigenvectors $v_{\pm}$ are given in this basis by $$v_+ = \frac{1}{\sqrt{2}}\begin{pmatrix}1\\i\\0\end{pmatrix}, \qquad\text{and}\qquad v_+ = \frac{1}{\sqrt{2}}\begin{pmatrix}1\\-i\\0\end{pmatrix}. $$ This corresponds to $$v_{\pm} = (u_1 \pm iu_2)/\sqrt{2},$$ as before.