Force (as a 3-vector) is not an invariant in special relativity. Whilst different observers agree that the charge is being accelerated, they will disagree on what that acceleration is and disagree on what electromagnetic fields are responsible for the acceleration.
To directly answer your first question, the velocity is measured in the frame of an observer who says that the magnetic field is ${\bf B}$.
Observers in other moving frames will measure a different magnetic field and measure an electric field. They will say that the force on the charged particle is different, but is still given by $q({\bf E}' + {\bf v}'\times {\bf B}')$, where the primes indicate quantities measured in an alternate inertial reference frame.
The magnetic part of the Lorentz force acts in a particular direction because that is the definition of the B-field. It is that field which is deemed responsible for a force $q{\bf v}\times {\bf B}$ in the frame of reference where a charge moves with velocity ${\bf v}$.
Why is there a force at all? Well if there is a frame of reference where there is just a B-field, then if you move to the stationary frame of the charged particle there will also be an E-field. This will apply a force on the charge in a particular direction, and whilst different observers will not agree on the force (see above), they will agree that the charge is being accelerated according to the transformation rules of special relativity - which requires the magnetic component of the Lorentz force to act in the direction given by ${\bf v}\times {\bf B}$.
The underlying symmetry of the situation is broken by the direction of relative motion between the two observers.