The direction of angular velocity is different from that of regular velocity for (arguably) two reasons. First, it points out of the plane because of the nature of angular velocity. It signifies a rotation, as such, there is not any particular direction unit vector in every coordinate space that could represent it. In spherical or cylindrical coordinates, it would of course be easy to assign it to the $\hat\theta$ direction, but what about systems like Cartesian coordinates? Thus, to signify the direction of something that points in every direction on a plane, it is easy to specify it along the one direction we can be sure the velocity isn't pointing - normal to the plane. This is a much used convention (such as with area vectors, torque, and many others). As usual as well, we use the Right Hand Rule.
The second, and perhaps more important reason is that we always want to ensure that the angular velocity does not correspond to any true velocity that would be moving in a radial direction. However, to convert angular velocity to true velocity, it is necessary to multiply by the radius (for the most part). Therefore, the equation:
$$\vec v=\vec\omega\times\vec r$$
is used. This allows us to define it in such a way that the true velocity never has a radial component due to the angular velocity.
The essence of the question is the definition of the angular velocity and its relation to the axis of rotation.
First of all, to describe the rotation of a single particle, one requires an axis of rotation $\hat{\mathbf{n}}$, and a rate of change of ‘orientation’ (or ‘angular position’) $\frac{d \theta( \hat{\mathbf{n}}) }{d t}$ around that axis. Without these 2 pieces of information, “rotation” is meaningless.
Having the axis of rotation and a rate of change of orientation, one can define the angular velocity $\vec{\omega}$ as
$$
\boldsymbol{\omega} = \frac{d \theta}{d t} \, \hat{\mathbf{n}}
$$
which includes both pieces of information.
Notice that the angular velocity is parallel to the axis of rotation by definition, and has the same amount of ‘information’ as the particle velocity $\mathbf{v}$.
To clarify this further, consider the following figure which depicts the rotation in 3d space, and conforms to the example given in the question,
where the spherical-polar coordinates $\theta$ and $\phi$ are used as the azimuthal and polar angles, respectively and the zenith ($z$-axis) is taken to be parallel to $\hat{\mathbf{n}}$.
In the limit of infinitesimal change in time, $\Delta t \rightarrow 0$,
$$
\Delta \mathbf{r} \approx r \, \sin \phi \, \Delta \theta ~,
$$
and thus,
$$
\left| \frac{d \mathbf{r}}{d t} \right| = r \sin \phi \frac{d \theta}{d t} ~.
$$
One clearly observes that both the magnitude and the direction of $\frac{d \mathbf{r}}{d t}$ (which is perpendicular to the plane defined by the particle position $\mathbf{r}$ and the rotation axis $\hat{\mathbf{n}}$) are given correctly by the cross product
$$
\frac{d \mathbf{r}}{d t} = \hat{\mathbf{n}} \times \mathbf{r} \frac{d \theta}{d t} ~.
$$
Since $\frac{d \mathbf{r}}{d t} \equiv \mathbf{v}$ and $\hat{\mathbf{n}} \frac{d \theta}{d t} \equiv \vec{\omega}$, one obtains
$$
\mathbf{v} = \frac{d \mathbf{r}}{d t} = \boldsymbol{\omega} \times \mathbf{r} ~.
$$
Therefore, the instantaneous axis of rotation $\hat{\mathbf{n}}(t)$ and the instantaneous angular velocity $\vec{\omega}(t)$ are indeed parallel.
Finally, as shown by Gary Godfrey in a comment, one can obtain the correct relation for the angular velocity $\boldsymbol{\omega}$ in terms of the velocity $\mathbf{v}$ and position $\mathbf{r}$ as
\begin{align}
\mathbf{r} \times \mathbf{v} &= \mathbf{r} \times ( \boldsymbol{\omega} \times \mathbf{r} ) \stackrel{\text{BAC-CAB}}{=} \boldsymbol{\omega} \, (\mathbf{r} \cdot \mathbf{r} ) - \mathbf{r} \, (\mathbf{r} \cdot \boldsymbol{\omega}) \\
\Rightarrow \boldsymbol{\omega} &= \frac {(\mathbf{r} \times \mathbf{v}) + \mathbf{r} \, (\mathbf{r} \cdot \boldsymbol{\omega})}{r^2} ~.
\end{align}
This answer is based on Kleppner, D., and R. Kolenkow. “An introduction to mechanics”, (2ed, 2014), pp. 294–295. The figure is taken from the same source.
Best Answer
Say you're looking at the piece of paper on your desk; that is the $xy$ plane. You place a dot in the center of the paper; that's your origin.
Your angular momentum is $\vec{L}=\vec{r}{\times}m\vec{v}$. For this example, $\vec{\omega}$ points in the same direction as your angular momentum, because $\vec{L}=mr^2\vec{\omega}$.
The way I remember the directions for the right-hand rule are as follows:
Let's say the particle is on the paper, directly above the origin, and moving counterclockwise. Then, $\vec{v}$ points to the left edge of the page. The direction of $\vec{r}$ goes from the origin to the point, so it points to the top of the page.
My thumb points up, so this is the direction of $\vec{L}$, and hence the direction of $\vec{\omega}$.
Crane your hand around so that your middle finger points right and your index finger continues to point to the top of the page, and your thumb points down, which is the direction of $\vec{\omega}$ for clockwise motion.