Theorem 10.3.6 of Nicolaescu's notes prove elliptic regularity for a first order PDO. I noted that this PDO is allowed to be interpreted as a system of first order pde's. Now, given any linear, elliptic PDO, we can replace each derivative with a new variable and adjoin all definitions into a single system of equations that gives rise to a first order PDO. Unless ellipticity is destroyed by this order reduction, I don't see why we could not prove elliptic regularity in general from the special case proved in the theorem.
I fail to see why reducing the order of a PDE would destroy its ellipticity, is there something I am missing?
I think it would help to see an example to see why this fails. You are correct that an elliptic PDE like $-\Delta u = f$ can be reduced to first order by setting $\vec v = \nabla u$ to yield the system $$ \begin{cases} \nabla u = \vec v \\ -\nabla\cdot \vec v = f \end{cases} $$ which writing $\vec w := \binom{u}{\vec v}, A := \left(\begin{matrix} \nabla & 0 \\ 0 & -\nabla\cdot\end{matrix}\right), \vec F(\vec w) := \binom{\vec v}{f}$ can be written more abstractly as $A\vec w = \vec F(\vec w)$.
Now your question seems to imply that there is some first-order PDO that is equivalent to $-\Delta$ in terms of its properties. The problem is that in reducing the equation, you have also changed the right-hand side since it also depends on the original input variable. So neither of the possible first order operators here, $A$ and $A - F$ play the correct role (the first does not include all the relevant information about the $\vec w$ that solves the Laplace equation and $A - F$ includes the arbitrary function $f$ as a parameter). So just because you can reduce a partial differential equation does NOT mean you can 'reduce' a partial differential operator to first order.