As a solid example, I taught my kids vectors in primary and middle school. I barely had to teach them, it just was common sense to them in the context. Keep in mind that they are good at math, but they are no more able and much less experienced than early High School students. I went the traditional route and did it via Cartesian coordinates and physics. Once you know coordinates, the concept of arrows, vector addition and vector multiplication just come naturally.
I liked the example from kchrisman about adding apples and oranges for the youngest kids. That is seriously no harder than mid primary school to lean the notation, and late primary for scalar multiplication. Of course with no variables.
Dot-product was harder conceptually, but fairly easy mechanically. In physics "it just works", and that is all they needed. Using the apples and oranges example, doing a dot product with the price list for the final cost should be easy for middle schoolers. It is what it looks like on a supermarket docket - so it can't be that hard. Still fairly concrete without variables.
Vector variables for substitution can be introduced just after normal variables. It actually make more sense at the beginning for vectors, as you can use them just to save space writing down and make formulas clearer - while normal variables use the same room as the numbers they are replacing and are no clearer. Normal 1D variables only are useful with generalised functions, which is a more abstract concept than simple substitution in a particular context.
Along with vectors, my kids were able to use a computer algebra system, so once they had the vector concepts, using them was as easy as using single dimensions numbers. Because of this, they already have an intuitive concept of a mathematical "group" or "field" (though not technically accurate) as they use the same addition and scalar multiplication with vectors as the did with integers.
Once you know vectors, much of maths becomes more concrete and qualitatively easier, reducing the age at which students are able to grasp it. Solving simultaneous equations - what is the big deal about? Gaussian elimination is just scaling and adding vectors until you get the arrows you want. It is just like basic arithmetic (not quite - but you know what I mean). Maybe mid high school for 2 equations, later for 3 equations?
It was much easier learning vectors and dot products than learning the 'cos' function - the traditional equivalent. In fact I still haven't really taught them trig - vectors are just too natural and too powerful to bother for most applications. If you know vectors, Pythagorus, and ratios, you can do most things you ever want to do.
Add the ability to transform radial coordinates into vectors, and you have most of the rest. You will need to know unit vectors which is a step up from dot product. But IMHO coordinates of an arrow is more concrete than the ratios of a triangle, early high school should be fine for teaching it. I know that it is really just trig, but it is trig without the yucky trig concepts, just the idea of different ways of writing a vector.
Once you have unit vectors you can learn parallel and perpendicular vectors. Could probably learn at the same time as trig is currently taught. Just involves dot product times unit vector for parallel, and subtracting parallel for perpendicular. So technically just a small step from translating radial to Cartesian coordinates, but it requires some more abstract thinking that suits mid-high school. However, the vector method is much easier to use than trig in a computer algebra system.
I have recently taught them 2D cross product for areas (triangle and rhombus), and that did not come naturally at all, and it is not something they need yet. At least as abstract as trig, but the mechanics are much more down to earth. Direct, easy multiplication and addition rather than via trig ratios. For appropriate problems, it may save you from the sine rule or cosine rule, and anything that can achieve that for even a few problems has to be a good thing! Probably upper high school.
If you want to rotate vectors directly rather than through radial translation, I think complex arithmetic is probably easier than introducing transformation matrices. If the student has been using vectors through high school, complex arithmetic should be easier to understand, but probably best left to last year of high school.
I suspect the biggest problem is that most teachers, school administrators and parents don't know vectors, and it doesn't have the kind of hero worship that calculus has, so it is really hard to get into a curriculum. Combine with the current "back to basics" movement ...