It suffices to calculate $\mathbb E ( (P_E)_{ab} (P_E)_{cd})$ for all $1\leq a,b,c,d\leq n$, or, equivalently, calculate $\mathbb E( P_E \otimes P_E ) \in \mathbb R^n \otimes \mathbb R^n \otimes \mathbb R^n \otimes \mathbb R^n$.
This is an $O(n)$-invariant tensor. The space of $O(n)$-invariant tensors in $\mathbb R^n \otimes \mathbb R^n \otimes \mathbb R^n \otimes \mathbb R^n$ is three-dimensional, generated by the three "diagonal" tensors. Thus
$$\mathbb E ( (P_E)_{ab} (P_E)_{cd}) = C_1 \delta_{a=b}\delta_{c=d}+ C_2 \delta_{a=c} \delta_{b=d} + C_3 \delta_{a=c} \delta_{b=d}$$ for some $C_1, C_2, C_3 \in \mathbb R$.
We have $$ m^2 = \sum_{i=1}^n (P_E)_{ii} \sum_{j=1}^n (P_E)_{jj} = \sum_{i=1}^n \sum_{j=1}^n \mathbb E ( (P_E)_{ii} (P_E)_{jj}) = n^2 C_1 + n C_2 + n C_3 $$
We have $$ m = \sum_{i=1}^n \sum_{j=1}^n (P_E)_{ij}^2 = \sum_{i=1}^n \sum_{j=1}^n \mathbb E ( (P_E)_{ij} (P_E)_{ji}) = n C_1 + n C_2 + n ^2 C_3 $$
and similarly
$$ m = \sum_{i=1}^n \sum_{j=1}^n (P_E)_{ij}^2 = \sum_{i=1}^n \sum_{j=1}^n \mathbb E ( (P_E)_{ij} (P_E)_{ij}) = n C_1 + n^2 C_2 + n C_3 $$
This gives $$C_1 = \frac{(m^2-m) (n+2) + m (n-m)}{n (n-1) (n+2) } , C_2 = \frac{m (n-m)}{ n (n-1)(n+2)}, C_3 = \frac{ m (n-m)}{ n (n-1) (n+2) } $$
We have
$$\mathbb E \left[ \left( \sum_{i=1}^k x_i^T P_E y_i\right)^2 \right] = \mathbb E\left[ \sum_{i=1}^k \sum_{j=1}^k x_i^T P_E y_i x_j^T P_E y_j \right]$$ $$ = C_1 \sum_{i=1}^k \sum_{j=1}^k (x_i \cdot y_i) (x_j \cdot y_j) + C_2 \sum_{i=1}^k \sum_{j=1}^k (x_i \cdot x_j) (y_i \cdot y_j) + C_3 \sum_{i=1}^k \sum_{j=1}^k (x_i \cdot y_j) (y_i \cdot x_j) $$
Your first term vanishes by assumption, so we get
$$ \frac{m (n-m)}{ n (n-1) (n+2) } \left( \sum_{i=1}^k \sum_{j=1}^k (x_i \cdot x_j) (y_i \cdot y_j) + C_3 \sum_{i=1}^k \sum_{j=1}^k (x_i \cdot y_j) (y_i \cdot x_j) \right).$$
Expressed in terms of the matrix $M = \sum_{i=1}^k x_i y_i^T$, this is
$$ \frac{m (n-m)}{ n (n-1) (n+2) }\operatorname{tr}( M M^T + M^2).$$
