Why does torque point perpendicular to direction of the motion?

To add to Steeven's answer and in particular his very pertinent statement:

You can't define a vector direction as something that turns around.

It may help you to understand that torque as a vector is actually cheating a little bit: it's a "simplification" that we can only get away with in two and three dimensions, which is why the "direction" seems a little abstract. The torque "vector" direction defines the axis of the motion that it tends to induce, and for the same reason that torque as a vector is a bit of a trick, even the notion of axis only works in two and three dimensions.

Torque is about rotation, and rotations primarily are about transformations that are confined to planes. For example, a rotation about the $z$-axis is a transformation that churns up the $x-y$ plane - it transforms the $x$ and $y$ co-ordinates of things - but leaves the $z$ co-ordinates unchanged.

When we do higher dimensional geometry, rotations change planes and leave more than one dimension invariant. In a four dimensional rotation, it's incomplete to speak of a rotation about an axis, because, for example, you can have a rotation that transforms the $x$ and $y$ co-ordinates of points invariant, but it leaves the $z$ and $w$ co-ordinate invariant.

So, in general, the easiest way to specify a rotation is by specifying the plane that it changes, rather than specifying the subspace that it leaves invariant.

It just so happens that in three dimensions, the subspace left invariant is a line or an "axis"- so the two approaches amount to the same thing. We can define a plane in three dimensions by specifying a vector normal to it, which is why we can get away with a torque or angular velocity as a vector. In general these quantities are directed planes, not lines with direction.

How can the bolt turn clockwise if the force is concentrated perpendicular to where it needs to turn?

Because that force is perpendicular to the direction towards the rotation-centre. Not to the turning direction. The bolt does indeed turn in the same way as the force pulls it.

When you define a torque vector direction, you have a problem. You can't define a vector direction as something that turns around. The direction must be along a straight line. So instead of choosing the torque "turn", we could choose the torque axis as the vector direction.

Have a look at this picture:

The axis is vertical through the bolt along the two upwards/downwards arrows. If you choose to define the torque vector direction along this axis, all fits. We just have to remember that choice.

Torque is: $$\vec \tau = \vec F \times \vec r$$

The force vector $\vec F$ times the vector towards the rotation-centre $\vec r$ gives the torque vector. The result of a cross-product is mathematically a vector pointing vertically upwards, so this fits perfectly to that choice. The torque vector $\vec \tau$ that you get from this calculation has the torque magnitude but the torque-axis direction.

As long as you remember this choice - this definition - all is good. Everytime you hear "the direction of the torque is horizontal", you know that this is only the axis of the torque; the torque (the turn) is then upright.

Consider the definition of torque $\vec{\tau}$ due to a force $\vec{F}$ passing through a point $\vec{r}$ $$\vec{\tau} = \vec{r} \times \vec{F}$$

Using the cross product identity $\| \vec{A} \times \vec{B} \| = \| A \| \|B \| \sin \theta$ where $\theta$ is angle formed by the two vectors we can write the following

$$ \| \vec{\tau} \| = \| \vec{r} \| \| \vec{F} \| \sin \theta $$ $$ \tau = F (r \cos \varphi) = F \, d$$ since $\theta = \frac{\pi}{2}+\varphi$ and $d = r \cos\varphi$ is the perpendicular distance to the force line of action.

In Summary, the cross product removes any influcence of the location of the force along the line of action and only considers the perpendicular distance for measuring torque.

Appendix

Torque is the moment of the line of action of a force. It is defined as $\vec{\tau} = \vec{r} \times \vec{F}$

Velocity is the moment of the line of rotation of a rigid body. It is defined as $\vec{v} = \vec{r} \times \vec{\omega}$

Both quantities ($\vec{\tau}$ and $\vec{v}$) contain the information about the distance (position) to a line in space. This can be recovered by

$$ \begin{align} \vec{r}_{\perp} &= \frac{\vec{\omega} \times \vec{v}}{\| \vec{\omega} \|^2} & \vec{r}_{\perp} &= \frac{\vec{F} \times \vec{\tau}}{\| \vec{F} \|^2} \end{align} $$

The direction of the torque vector is similar to the direction of the velocity vector on a rotating rigid body. It is a circumferential vector perpendicular to both the line of action and the location of the line. It is best explained motion motion as the tangential velocity of an extended rotating body under the coordinate origin.

_{See this answer for a more detailed explanation of the geometry in mechanics.}