There are a couple of things going on here. Firstly, in general a rotation occurs in a two dimensional plane - this works in 2, 3, 4, ... dimensions. (BTW, to head off that person in the comments, everything I am saying here is about flat, Euclidean, vanilla geometry).
Now in two dimensions, there is only one plane to rotate in, so all we have to do is decide on a sign convention, usually this is counterclockwise = positive (who came up with clocks anyway?)
When we move to three dimensions, things get a little more complicated ... and something magical happens.
Now, there are many choices of plane available to us, and to specify a rotation, we need to pick a plane and specify an angle. In three dimensions, we have at our disposal the fact that every choice of plane can be specified by a vector normal (i.e. at right angles) to the plane. That is where this convention comes from ... it is a really convenient way to specify a plane in 3D.
NB this is closely related to the existence of the cross product in three dimensions: the cross product of a pair of (independent) vectors is normal (again, at right-angles) to the plane "spanned" by those vectors (i.e. the plane of all linear combinations of the pair of vectors).
Now in four (or higher) dimensions, you cannot specify a plane of rotation using just one vector normal to it. e.g. In four dimensions, the space orthogonal to any given plane is two dimensional ... so you would need two vectors to specify it and you may as well just describe vectors in the original plane of rotation. In general, in $n$ dimensions, the orthogonal space is $(n-2)$-dimensional, so it's only in 2 and 3 dimensions that there is any profit in using an alternate representation of the plane.
- Planes of rotation are actually 2-dimensional things
- In 3D something special happens where you can specify that plane using a single vector (the vector of rotation) - this is related to the cross-product
- The vector of rotation is used by convention, it has no physical significance on its own
- If you are trying to build your intuition, focus on the plane-of-rotation, and just recognize the vector-of-rotation as a handle sticking out of it