What Stokes' Theorem tells you is the relation between the line integral of the vector field over its boundary $\partial S$ to the surface integral of the curl of a vector field over a smooth oriented surface $S$:
$$\oint\limits_{\partial S} \mathbf{F} \cdot d\mathbf{r} = \iint\limits_S (\nabla \times \mathbf{F}) \cdot d\mathbf{S} \tag{1}\label{1}$$
Since the prompt asks how to calculate the integral using Stokes' Theorem, you can find a good parametrization of the boundary $\partial S$ and calculate the "easier" integral of the LHS of (1).
Note that the boundary of $S$ is given by:
$$\partial S=\{(x,y,z)\in \mathbb R^3 : x^2 +y^2 =25, z=0\},$$
so a good parametrization to use for $\partial S$ could be:
$$\sigma :[0,2\pi] \subseteq \mathbb{R} \rightarrow \mathbb R^3$$ $$\sigma(\theta)=(5\cos(\theta),5\sin(\theta),0)$$
and finally the integral to calculate ends up being:
$$\begin{align}\oint\limits_{\partial S} \mathbf{F} \cdot d\mathbf{r}&= \iint\limits_S (\nabla \times \mathbf{F}) \cdot d\mathbf{S} \\ &=\int_{0}^{2\pi}(0,5\cos(\theta),e^{25\cos(\theta)\sin(\theta)})\cdot(-5\sin(\theta),5\cos(\theta),0)\, d\theta,\\&=\int_{0}^{2\pi}25\cos^2(\theta)\,d\theta\end{align}$$
and from here you can use trigonometric identities to calculate the last integral.
I hope that helps!
I'll start with some critique. First of all, your normal vector isn't quite correct: from the equation of the plane $-2x+z=0$, we get the normal vector $\mathbf{n}=\langle-2,0,1\rangle$ (or it could be its opposite, but this one gives the upward orientation, consistent with the counterclockwise orientation of the curve $C$). Fortunately, it doesn't affect your solution because the first component of curl is zero.
Second, it is a really bad habit to drop differentials, representing the variables of integration, from integral notation! For example, the last line of your computation should be written as
$$\iint_S (2x-xz)\,dx\,dy=\iint_S (2x-2x^2)\,dx\,dy=\int_{-\pi/2}^{\pi/2}\int_0^{2\cos\theta} (2r\cos\theta-2r^2\cos^2\theta)r\,dr\,d\theta.$$
Third, you must be much more clear regarding domains of integration. The "equality"
$$\iint_S \operatorname{curl}F\cdot\mathbf{n}\,dS=\iint_S (2x-2x^2)\,dx\,dy$$
is wrong because the domains of integration in these two integrals are NOT the same and thus cannot be denoted by the same letter $\color{red}{S}$. If $S$ stands for the portion of the plane cut out by the paraboloid (or cylinder), then it's rightfully used in the first integral, but not in the second. The second one represents a double integral over a region $D$ in the $xy$-plane after you effectively parameterized the surface $S$. And this region $D$ is the disk $(x-1)^2+y^2=1$, that you correctly found. And to integrate over this $D$, it certainly makes sense to switch to polar coordinates.
In the end of the day, you did get a correct double integral in polar coordinates (also see above), so you can finish solving this problem by evaluating that integral. (I presume you can do that, and you don't need us to give you the answer.)
Now, a very short main answer to your main question: YES, we are allowed to choose any such surface. :-)
Best Answer
An approach to the definition of the basic 3D vector differential operators by using the Gauss-Green and Stokes theorems has been sometimes used by mathematicians and mathematical physicists: to my knowledge, the most complete work on such topic was done by Claus Müller in the monograph [1]. The approach is of some importance since it does not require any differentiability condition on the fields involved.
Precisely, without the use of distribution theory, and instead by using the integral definition of standard vector operators, he defines a sort of weak derivatives in the following way: $$ \nabla\times \boldsymbol{F} =\lim_{S_i\to x}\frac{1}{\Vert S_i\Vert}\int\limits_{\partial{S_i}} \boldsymbol{n}\times \boldsymbol{F}\,\mathrm{d}\sigma\triangleq\mathrm{curl}\,\boldsymbol{F}\tag{1}\label{1} $$ where
Considering your case, you should chose a contractible surface $S$ in order to contract to the point $(x,y,z)$ where you want to find the value of $\mathrm{curl}\,\boldsymbol{F}$, and then compute the limit in \eqref{1}
[1] Claus Müller (1969)[1957], Foundations of the Mathematical Theory of Electromagnetic Waves, Grundlehren der mathematischen Wissenschaften 155, Springer-Verlag, pp. VIII+353, MR0253638, Zbl 0181.57203.