For the first integral you can use Stokes' Theorem directly and compute the surface integral over a surface $M$ as a line integral over the boundary $\partial M$ (properly oriented):
$$\iint_M (\nabla \times F) \cdot \hat{n} d\sigma = \int_{\partial M} F\cdot \hat{T} ds$$
For the second, you have to find a vector potential for $F$ - that is, to express $F$ as $\nabla \times G$ for some to-be-determined-by-you vector field $G$:
$$\iint_M F\cdot \hat{n} d\sigma = \iint_M (\nabla \times G) \cdot \hat{n} d\sigma = \int_{\partial M} G\cdot \hat{T} ds$$
So:
"Can we use Stokes's Theorem to calculate the flux of a vector field across a surface?" Yes, if you find a vector potential for the given vector field. Since the divergence of a curl is zero, that would not be possible if the divergence of $F$ were not zero.
"Can we use a surface integral to calculate the flux of the curl across a surface in the direction of the normal vector?" Yes, but the computation would likely be simplified by using Stokes' Theorem - hence computing a line integral instead of a surface integral.
The paraboloid $z=x^2+y^2$ and the plane $z=ax+by$ intersect for
$$x^2+y^2=ax+by\implies\left(x-\frac a2\right)^2+\left(y-\frac b2\right)^2=\frac{a^2+b^2}4$$
i.e. in the cylinder with cross sections parallel to the $x$-$y$ plane centered at $\left(\frac a2,\frac b2\right)$ with radius $\frac{\sqrt{a^2+b^2}}2$. Naturally, I think this suggests a parametrization of $S$ in cylindrical coordinates,
$$\hat s(u,v)=x(u,v)\,\hat\imath+y(u,v)\,\hat\jmath+z(u,v)\,\hat k$$
where
$$\begin{cases}x(u,v)=u\cos v+\frac a2\\[1ex]y(u,v)=u\sin v+\frac b2\\[1ex]z(u,v)=x(u,v)^2+y(u,v)^2=\frac{a^2+b^2}4+u^2+au\cos v+bu\sin v\end{cases}$$
with $0\le u\le\frac{\sqrt{a^2+b^2}}2$ and $0\le v\le2\pi$.
From the integrand we can obtain the underlying vector field $\hat F$:
$$y^2\,\mathrm dz=\underbrace{(0\,\hat\imath+0\,\hat\jmath+y^2\,\hat k)}_{\hat F(x,y,z)}\cdot(\mathrm dx\,\hat\imath+\mathrm dy\,\hat\jmath+\mathrm dz\,\hat k)$$
Compute the curl:
$$\nabla\times\hat F=2y\,\hat\imath$$
Take the normal vector to $S$ to be $\hat n=\frac{\partial\hat s}{\partial v}\times\frac{\partial\hat s}{\partial u}$:
$$\hat n=\frac{\partial\hat s}{\partial v}\times\frac{\partial\hat s}{\partial u}=(au+2u^2\cos v)\,\hat\imath+(bu+2u^2\sin v)\,\hat\jmath-u\,\hat k$$
Then by Stokes' theorem the integral is
$$\begin{align*}
\oint_Cy^2\,\mathrm dz&=\oint_C\hat F\cdot\mathrm d\hat r\\[1ex]
&=\iint_S(\nabla\times\hat F)\cdot\mathrm d\hat S\\[1ex]
&=\int_0^{2\pi}\int_0^{\sqrt{a^2+b^2}2}\left(2y(u,v)\,\hat\imath\right)\cdot\hat n\,\mathrm du\,\mathrm dv\\[1ex]
&=2\int_0^{2\pi}\int_0^{\sqrt{a^2+b^2}/2}\left(u\sin v+\frac b2\right)\,\mathrm du\,\mathrm dv\\[1ex]
&=\boxed{2\pi b\sqrt{a^2+b^2}}
\end{align*}$$
Best Answer
As the orientation of the rectangle is not given, here I will assume clockwise orientation (as seen from top). We can first find the plane on which the rectangle lies.
We can get directional vectors of two lines from the vertices $A(0,0,0), B (1,0,0), C (1,4,4), D (0,4,4)$
$\vec{AD} = (0-0,4-0,4-0) = (0,4,4), \vec{DC} = (1-0,4-4,4-4) = (1,0,0)$
So normal vector of the plane $\vec{N} = \vec{AD} \times \vec{DC} = \begin{vmatrix} i & j & k \\ 0 & 4 & 4 \\ 1 & 0 & 0 \end {vmatrix} = \, (0,4,-4)$
And equation of the plane is $ \, z = y$.
Unit vector $n = \frac{\vec{N}}{||N||} = \frac{(0,4,-4)}{4\sqrt2} = \frac{(0,1,-1)}{\sqrt2}$, $dS = \sqrt2 dA$ (as $|n \cdot k| = \frac{1}{\sqrt2}$).
So, $\int \int (curl F) \cdot n dS = \int \int (curl F) \cdot (0,1,-1) dA$ ...(i)
$ curl F = \nabla \times F = \begin{vmatrix} i & j & k \\ \frac{\partial}{\partial x} & \frac{\partial}{\partial y} & \frac{\partial}{\partial z} \\ z^2 & -x^2 & 0\end {vmatrix} = \, (0,2z,-2x)$
Now using $z = y$ from the equation of the plane and we can integrate using (i)
$\int \int (curl F) \cdot n dS = \int_0^4 \int_0^1 (0,2y,-2x) \cdot (0,1,-1) \, dx \, dy$
$ = 2 \int_0^4 \int_0^1 (x + y) \, dx \, dy = 20$