\begin{eqnarray} \text{cov}(\bar X_n, \bar Y_n) &=& \text{cov}(1/n \sum X_i, 1/n \sum Y_j)\\ &=& 1/n^2 \cdot \text{cov}( \sum X_i, \sum Y_j)\\ &=& 1/n^2 \cdot \sum_i \sum_j \text{cov}( X_i, Y_j) \end{eqnarray}
To go further, we need to specify something about the covariances. If the samples are iid random samples where $\text{cov}(X_i,Y_j)$ is constant over all $i,j$:
\begin{eqnarray} \quad\quad &=& 1/n^2 \cdot n^2 \text{cov}( X, Y)\\ \quad\quad &=& \text{cov}( X, Y)\, . \end{eqnarray}
If instead (and as seems to be the case here) we're talking about paired data, where $X_i$ and $Y_j$ are only correlated when $i=j$ then:
\begin{eqnarray} \quad\quad &=& 1/n^2 \cdot \sum_i \sum_j \text{cov}( X_i, Y_j)\\ \quad\quad &=& 1/n^2 \cdot n \cdot \text{cov}( X_i, Y_i)\\ \quad\quad &=& 1/n \cdot \rho\, \sigma_x \sigma_y, \end{eqnarray}\begin{eqnarray} \quad\quad &=& 1/n^2 \cdot \sum_i \sum_j \text{cov}( X_i, Y_j)\\ \quad\quad &=& 1/n^2 \cdot n \cdot \text{cov}( X_i, Y_i)\\ \quad\quad &=& 1/n \cdot \text{cov}( X_i, Y_i)\\ \quad\quad &=& 1/n \cdot \rho\, \sigma_x \sigma_y, \end{eqnarray}
where $\rho$ is the correlation between $X$ and $Y$ pairs.