Measuring distance preservation in dimensionality reduction
The confusion

The point of confusion is probably the use of variable $n$ to denote the dimension in Euclidean distance, which is later re-used for the number of points. Euclidean distance is better to be written as
$$d_X(\boldsymbol{x}_1, \boldsymbol{x}_2)=\sqrt{\sum_{i=1}^{\color{red}{d}}(x_1^i - x_2^i)^2}$$
in the original space, and
$$d_Z(\boldsymbol{z}_1, \boldsymbol{z}_2)=\sqrt{\sum_{i=1}^{\color{red}{k}}(z_1^i - z_2^i)^2}$$
in the reduced space. Where $\boldsymbol{z}_a=(z_a^1,\cdots,z_a^k)$ is the transformation of point $\boldsymbol{x}_a=(x_a^1,\cdots,x_a^d)$ by $W$. EDIT: in your notation, $Z[:, a]$ is the transformation of $X[:, a]$.

Distance preservation measure

A measure of distance preservation for transformation $W$ should be defined in such a way that compares the distance of two points in the original space with the distance of the same two points in the reduced space. 

Accordingly, a measure that compares all $\binom{n}{2}$ pairwise distances could be defined as:
$$DP(W) = \frac{2}{n(n-1)}\sum_{a=1}^{n} \sum_{b=a+1}^{n} |d_X(\boldsymbol{x}_a, \boldsymbol{x}_b) - d_Z(\boldsymbol{z}_a, \boldsymbol{z}_b)|$$

where for a constant $k$, smaller $DP(W)$ implies better distance preservation by $W$.

Note that various measures of distance preservation can be defined based on this foundation. For example, 


Restricting the comparison to only $K$ nearest neighbors of a point in the original space, leading to $nK$ comparisons instead of $\binom{n}{2}$, or 
Using the Pearson correlation of distances rather than their difference, since we generally want close (distant) points in the original space to be also close (distant) in the reduced space, or
Measuring the distance to point's tangent space instead of the point itself, etc.