In the restated problem both $X$ and $Y$ have rank at most $k \ll n$, and the same is true of Gram matrices $A$ and $B$. Also $C=(X+Y)(X+Y)^T$ will have rank at most $k$.
The goal of forming $C$ from $A$ and $B$, even approximately, seems unattainable. To briefly enlarge upon Jack Poulson's example, let $X$ and $Y$ be any two matrices such that:
$$ XX^T = YY^T = \begin{pmatrix} I & 0 \\ 0 & 0 \end{pmatrix} $$
where the given nonzero block $I$ is $k \times k$. Thus $X,Y$ might be of this form:
$$ X = \begin{pmatrix} P \\ 0 \end{pmatrix} $$
$$ Y = \begin{pmatrix} Q \\ 0 \end{pmatrix} $$
where $P,Q$ are $k \times k$ orthogonal matrices.
Taking $Q = I$ for simplicity, we see that:
$$ C = (X+Y)(X+Y)^T = 2 \begin{pmatrix} I+P & 0 \\ 0 & 0 \end{pmatrix} $$
So Jack's point is that the problem is not well-defined without further constraints. Knowing $A = XX^T$ and $B = YY^T$ is insufficient to approximate $C$, as $P$ might be any orthogonal matrix of the right size.
Let me suggest that computing $C$ from $A$ and $B$ might be the wrong goal. After all, storing $A$ rather than $X$ (resp. $B$ than $Y$) takes more space, since $X$ is only $n \times k$, but $A$ would generally be a full $n \times n$.
Ordinarily a programmer would be pleased to store the factors $X$ (resp. $Y$) and to do the fairly easy update $X+Y$ rather than compute and store $C$. Saves time, saves space.
Of course one might fear that further operations done implicitly with $C$ using $X+Y$ are less efficient. This is not so, at least with a wide range of studied numeric applications. Consider for example forming a matrix-vector product $Cv$. With explicitly formed $C$ this takes $n^2$ multiplications (and roughly equal number of adds). Doing the implicit product by associativity $(X+Y)(X+Y)^Tv$ only takes $2kn$ multiplies (resp. adds).
