About eigenvalues of probability matrices

The answer to your first question is given in Corollary 5.2, as the paper states. Because $R$ is symmetric, it has an orthonormal basis consisting of eigenvectors. The largest eigenvalue is $\lambda_1 := 1$ with multiplicity $1$, and the corresponding eigenvector $v_1$ is the vector of all $1$s. Therefore, any $x$ orthogonal to the all $1$s vector is a linear combination of the other eigenvectors $v_2, \ldots, v_n$ of $R$, e.g. $x=c_2 v_2 + \cdots + c_n v_n$ and you can check that $$x^\top R x = c_2^2 \lambda_2 + \cdots + c_n^2 \lambda_n \ge (c_2^2 + \cdots + c_n^2) \lambda_2 = \lambda_2 \|x\|^2.$$

For your second question, it is not that $(L^\top)^2 x = x$, but rather that $1^\top (L^\top)^2 = 1^\top$, or equivalently, $L^2 1 = 1$. Just use the fact that the rows of $L$ sum to $1$.