Efficient Robust Private Set Intersection Questions
In general, you might find it more useful to look at the full description of the protocol on page 137 of the paper you cite, rather than the general overview on the preceding pages.

To answer your specific questions:


From page 137, step 8 (which corresponds to step 7 in the general overview):


  "For each $y_j \in Y$, $S$ chooses a random polynomial $P_{0,j}$ of degree $k + k (\lfloor \log n \rfloor + 1)$ with constant coefficient equal to $0$..."


To choose a random polynomial, you just choose every coefficient (except the lowest one, since that's specified to be zero) uniformly at random from the field you're using.
From page 137, step 9:


  "For each $y_j \in Y$, for $1 \le i \le 10k(\lfloor \log n \rfloor + 1)$, using the sharing polynomials obtained in Steps 6, 7, 8, and a random value $r_{i,j}$, $S$ computes: $Out_{i,j} = $..."

See section 2, "Deﬁnitions and Building Block Protocols" on pp. 127&ndash;128.  It looks to me like the choice between using a comma or a semicolon to separate the arguments to $\rm ENC$ is merely a stylistic / typographical one: ${\rm ENC}(x,r)$ and ${\rm ENC}(x;r)$ should mean the same thing.
Yes, there presumably is, although I cannot absolutely confirm that for you without actually reading the whole paper.