Puedes obtener una parametrización de tu subvariedad al verla como un gráfico de una función, y las derivadas parciales de la parametrización dan una base del espacio tangente en cada punto.
Sea el paraboloide, como una subvariedad, denotado por $S$. Tenemos $f(x,y) = (x, y, x^{2} + y^{2})$ como nuestra parametrización, por lo tanto $T_{f(x,y)}S = <(1,0,2x)^{t}, (0,1,2y)^{t}>.
Ahora obtienes exactamente dos vectores de longitud unitaria que abarcan el complemento ortogonal de $T_{f(x,y)}S$. Elige un vector así, llamémoslo $\nu$. Todo lo que tienes que hacer ahora es encontrar el plano al que deseas que $T_{f(x,y)}S$ sea paralelo, y verificar que la recta definida por $c(t) = f(x,y) + t\nu$ intersecte el plano de manera ortogonal.
Editar:
Para la última parte, utilizamos que en el espacio euclidiano, un hiperplano es paralelo a otro hiperplano si y solo si existe una recta que se encuentra con ambos ortogonalmente.