Is there a fast algorithm for computing the matrix square root of a real symmetric matrix using random matrices or randomized algorithms?
Randomized algorithms can accurately approximate your matrix if it has rapidly decaying singular values (i.e. a Gaussian sampling of the range is likely to pick up the action of the matrix). Since your matrix is symmetric, you could approximate a truncated eigenvalue decomposition using random linear algebra and simply take the square root of the eigenvalues.
I'm not sure of any explicit algorithms based on randomized linear algebra (RLA) which approximate the matrix square root explicitly. You could also try iterative algorithms for the matrix square root (Wikipedia shows a few examples) and try to exploit RLA there in matrix-vector multiplications or applying matrix inverses, though this may not work well since inverses typically need the smallest singular values.