It is impossible.
Let $V=\begin{bmatrix} v_1 \cdots v_k\end{bmatrix}$, and $G_V=V^TV$.
Note that if $U \in O(n)$, we have $G_V = (U V)^T UV = G_{UV}$.
Suppose that given input $G$, an algorithm produces an output $B$.
Then the same algorithm will produce $B$ for both $G_V$ and $G_{UV}$, where $U \in O(n)$. However, if $B=AV$ for some $A \in SO(n)$, then we must also have $B=A' UV$ for some other $A' \in SO(n)$. Since we may choose $U$ with $\det U = -1$, we have a contradiction.
Addendum to address comments below by Marc:
If the requirement $A \in SO(n)$ is relaxed to $A \in O(n)$ instead, then, as @adam w noted in the comments above, one can use the Cholesky decomposition. Since $G=G^T$ and $G\geq 0$, $G$ has a Cholesky decomposition $G = L L^T$ ($L$ is lower triangular, but that is not important here). Since we have $V^T V = L L^T$, we can show that there exists a $U \in O(n)$ (not necessarily unique) such that $V = UL^T$ (it follows from the fact that $\|Vx\| = \|L^T x\|$ for all $x$), and hence we have $L^T = U^T V$. Letting $A=U^T \in O(n)$ shows that $L^T$ does the job.