Q1: generating a random primitive binary polynomial
Yes, the best known way to generate a random primitive binary polynomial of a given degree $p$ is to randomly generate a binary polynomial of degree $p$ with an odd number of terms, including $x^p$ and $1$; and test if it is primitive; until finding a primitive one.
For some $p$, it is possible to find a trinomial (see the list of all primitive trinomials for $p\le400$); for other $p$, at least a pentanomial is necessary (see this list of one primitive pentanomial with about equally spaced coefficients for each $p\le660$); and it is conjectured always sufficient (see this answer).
The most involved part is testing primitiveness. We can use that a LFSR using a polynomial of degree $p$ has period $2^p-1$ starting from some non-zero state if and only if its polynomial is primitive.
- We compute the state of the LFSR after $2^p-1$ steps starting from $1$ (there's an easy $\mathcal O(p^3)$ algorithm for that), and check that is $1$ (otherwise, the polynomial is not primitive and we stop).
- After that check, it only remains to check that the actual period is not smaller. A deterministic algorithm uses that the period must divide $2^p-1$. So, for each prime $q$ dividing $2^p-1$, we compute the state of the LFSR after $(2^p-1)/q$ steps starting from $1$, and check that's not $1$ (otherwise, the polynomial is not primitive and we stop).
Factoring $2^p-1$ is difficult, but The Cunningham Project can come to the rescue with the factorization of all $2^p-1$ for odd $p<991$, and then some. I think there is a randomized algorithm that does not require factoring $2^p-1$, but I fail to find a reference.
Q2: Yes you can use a random number generator to generate $a$ and $b$; make that a cryptographically strong pseudo-random generator seeded by $S$, and repeat generating $a$ and $b$ until they meet constraints you have, and you should be done.
Q3: Except for small $p$, you do not want to generate all points on the curve; there are in the order of $\mathcal O(2^p)$, that's too much. For small $p$, you can indeed generate all points, and yes for a given $x$ finding the corresponding value(s) of $y$ reduces to a 2nd degree equation, which can be solved, and that saves time compared to trying all values of $y$.
Q4: Except for small $p$, Schoof's algorithm and the likes is the way to go; I can't help for this.