Essentially you are asking to raise the rotation matrix to an arbitrary power. To do this you can use the fact that $X^a=\exp(a \log X)$ for any matrix $X$. To compute the matrix logarithm we use
$$\log X = \log (I - (I-X)) = -\sum_{n=1}^\infty \frac{(I-X)^n}{n}$$
Now if you can diagonalize $I-X$ (perhaps there is a proof that this is always possible for $X$ a rotation matrix?) to give $I-X=SDS^{-1}$ then you have
$$\log X = -S \left(\sum_{n=1}^\infty \frac{D^n}{n}\right) S^{-1}$$
which is fast to compute (again you'd need a proof that this converges when $X$ is a rotation matrix). Now you compute the matrix exponential in the same way. Letting $\log X=\hat{S}\hat{D}\hat{S}^{-1}$ for $\hat{D}$ diagonal,
$$X^a = \exp(a\log X) = \hat{S} \left(\sum_{n=0}^\infty \frac{a^n \hat{D}^n}{n!}\right) \hat{S}^{-1}$$
which again is fast to compute.
Thinking off the top of my head now, it seems that since all rotations are in a plane, the eigenvalues of a rotation X in $\mathbb{R}^n$ must be $e^{\pm \mathrm{i}\theta}$ for some $\theta$ (once each) and $1$ ($n - 2$ times). Therefore the matrix $I-X$ has eigenvalues $1-e^{\pm\mathrm{i}\theta}$ and $0$ ($n - 2$ times), so its diagonalisation D has a particularly simple form.
The answer is yes, since the exponential map $\exp: \mathbf{so}(3) \rightarrow \mathbf{SO}(3)$ is surjective (=onto).
Long answer:
Axis-angle can be represented using a $3$-vector $\omega$ while the magnitude $\theta=|\omega|$ is the rotation angle and $\mathbf{u}=^\omega/_\theta$ is the rotation axis. 3-Vectors are closed under the cross product:
$$\omega_1\in \mathbb{R}^3, \omega_2\in \mathbb{R}^3\Rightarrow (\omega_1\times \omega_2)\in\mathbb{R}^3.$$
Each such vector $\omega$ has an equivalent $3\times 3$ matrix representation
$\hat{\omega}$ (which is uniquely defined by $\hat{\omega}\cdot \mathbf{a} := \omega\times \mathbf{a}$ for $\mathbf{a}$ being a general 3-vector).
The space of matrices of the form $\hat{\omega}$ is called the Lie algebra $\mathbf{so}(3)$. Thus, one can show that matrices of the form $\hat{\omega}$ are closed under the Lie bracket $[A,B]=AB-BA$:
$$\hat{\omega_1}\in \mathbf{so}(3), \hat{\omega_2}\in \mathbf{so}(3)\Rightarrow [\hat{\omega}_1, \hat{\omega}_2]\in\mathbf{so}(3).$$
Now, let us consider the matrix exponential: $\exp(\mathtt{A}) = \sum_{i=0}^\infty \frac{\mathtt{A}^i}{i!} $. Two poperties can be shown:
(1) If $\hat{\omega}\in\mathbf{so}(3)$, then $\exp(\hat{\omega})\in\mathbf{SO}(3)$.
$\mathbf{SO}(3)$ is the special orthogonal group in three dimensions. Thus, it consists of matrices which are orthogonal ($\mathtt{R}\cdot \mathtt{R}^\top=\mathtt{I}$) and the determinant is 1. In other word, it is the group of pure rotations.
(2) The exponential map $\exp: \mathbf{so}(3) \rightarrow \mathbf{SO}(3)$ is surjective.
So, (1) says that every $\exp(\hat{\omega})$ is a rotation matrix. And, (2) says that for each rotation matrix $\mathtt{R}$, there is at least one axis-angle
representation $\omega$ so that $\exp(\hat{\omega})=\mathtt{R}$
Proofs of (1) and (2) are in corresponding text books, e.g. [Gallier, page 24].
Best Answer
First of all, you'd have to make sure that the matrix actually is a rotation. When all eigenvalues have $|\lambda_k| = 1$, the matrix won't shear or distort. Then, $|\det A|=1$, too. If $\det A=1$, the matrix keeps handiness (that is, won't mirror), too. Then you could call the matrix a rotation. You'd still have the problem that there'd not need to be a single "axis of rotation".
If you do an eigenvalue decomposition, rotations in the ordinary sense (mapping real vectors to real vectors) will show up as eigenvalues $\lambda_k=1$ (mirror-rotations as $\lambda_k=-1$), associated to a real eigenvector of length $1$ that shows the rotation axis.
In the three-dimensional case, plainly speaking, there's always exactly one of these. The other two degrees of freedom will have complex eigenvalues and complex coordinates.
If there are more of three dimensions, we could still have rotation about an axis with a specific angle. However, this is a special case. You could as well have more than one axis. Still, I'd recommend the following path, if you "just" want to solve the problem computationally:
Additional reading:
https://en.wikipedia.org/wiki/Rotation_matrix https://en.wikipedia.org/wiki/Quaternions_and_spatial_rotation