Background: It is very convenient to use the following notation:
$\mathtt R_{UV}$ is a rotation matrix which transform points from reference frame $V$ into the reference frame $U$. Thus: $\mathbf x_U = \mathtt R_{UV} \mathbf x_V$.
The inverse rotation is $\mathtt R_{VU} = \mathtt R_{UV}^{-1}=\mathtt R_{UV}^\top$.
Lets, call the initial frame $O$. I assume you mean with "rotated from the same initial frame" a change in the observer frame/passive transformation (http://en.wikipedia.org/wiki/Active_and_passive_transformation).
Thus, you have the rotation matrices $\mathtt R_{OA}$ and $\mathtt R_{OB}$ (which describe the motion of the observer from $O$ to $A$/$B$, or in other words maps points from $A$/$B$ to $O$). Now, I assume you are interested in $\mathtt R_{AB} = \mathtt R_{AO}\mathtt R_{OB} = \mathtt R_{OA}^\top\mathtt R_{OB}$.
Finally, convert $\mathtt R_{AB}$ into axis-angle...
(In case you have $\mathtt R_{AO}$ and $\mathtt R_{BO}$ and want to calculate $\mathtt R_{BA}$ , you get $\mathtt R_{BA}=\mathtt R_{BO}\mathtt R_{AO}^\top$.)
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
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.