Lattice attacks against Multilinear Maps [CLT13]
1. Why can't we find the vectors $\mathbf{r}_i$ by Gaussian Elimination?

The problem here is that $\mathbf{r}_i$ are small. You can use Gaussian Elimination to recover vectors orthogonal to $(\mathbf{u}_1, ..., \mathbf{u}_{t-n})$, but the vectors found will not be short vectors.

2. How to get encodings in level-zero?

Actually, one does not get encodings in level-zero. All the encodings are in level-one, i.e. multiplied by $z^{-1}$  (inverse modulo $x_0$).

However, this is irrelevant for the attack because the definition of the orthogonal lattice is:

$$L=\{ \mathbf{u} \in \mathbb{Z}_{x_0}^t : \mathbf{u} \cdot \mathbf{x} = 0 \mod x_0 \}$$

Thus, considering encodings at level-one means that we have $\mathbf{x} \cdot z^{-1}$ instead of $\mathbf{x}$. Therefore, we are actually constructing the following lattice:

$$L'=\{ \mathbf{u} \in \mathbb{Z}_{x_0}^t : \mathbf{u} \cdot \mathbf{x} \cdot z^{-1} = 0 \mod x_0 \}$$

But since $\mathbf{u} \cdot \mathbf{x} \cdot z^{-1} = 0 \mod x_0 \Leftrightarrow \mathbf{u} \cdot \mathbf{x} = 0 \mod x_0$, it holds that $L = L'$. 

Hence, having $t$ encodings at level-zero or $t$ encodings at level-one is equivalent in this attack.