You can obtain a parametrisation of your submanifold by viewing it as a graph of a function, and the parametrisation's partial derivates give a basis of the tangent space at each point.
Let the paraboloid, as a submanifold, be denoted by $S$. We have $f(x,y) = (x, y, x^{2} + y^{2})$ as our parametrisation, hence $T_{f(x,y)}S = <(1,0,2x)^{t}, (0,1,2y)^{t}>$.
You now get exactly two unit-length vectors that span the orthogonal complement of $T_{f(x,y)}S$. Chose such a vector, let's call it $\nu$. Now all you have to do is find the plane you want your $T_{f(x,y)}S$ to be parallel to, and check that the line defined by $c(t) = f(x,y) + t\nu$ meets the plane orthogonally.
Edit:
For the last part, we use that in euclidian space, a hyperplane is parallel to another hyperplane iff there exists a line that meets both orthogonally.