only thing against mages would be to hope that they go OOM I guess. You do not have the abilities to counteract their constant kiting at least (missing intercept here and spell reflect). Smart use of bombs might get you close with hamstring (but I guess you already do that). SW when they pop icy veins as frost. I can't say when to trinket here, but perhaps a freedom of movement pot is actually needed for you to get him down.
Paladins are just hard because of their burts.
You should be able to open with charge and apply rend straight on, swap to defensive stance and disarm. Chances are that the paladin uses Hammer of Justice before you can disarm him, trinket out of it. While he is disarmed you have free dps time; so try to hit as much as you can for the 10 seconds. Make sure to apply thunderclap and demo shout just before disarm ends.
Swap stance to battle again and apply rend and hamstring and start making distance while going back to defensive stance. It might be a good idea to pop Last Stand here, seeing that he will be trying to burst you down. Make sure you get Shield Block up once your back in defensive stance. Hope for the paladin to use BoF to get back to you here. Eat the damage while BoF is up.
Hamstring and rend again while making more distance again, this time you should be able to get enough range to get out of combat and charge in again, or if he pops a trinket then you just got a gift from above.
When your back on him again from either a charge or because he catched up, you fear him and bandage (macro), do make sure your not standing in consecration.
Once he gets out of fear you need to eat some dmg before your disarm is of CD again, once it is it will be your turn again.
When he uses divine protection and stays hitting you then you pop SW. If he pops Hand of protection you move away or bandage if you can. When he uses lay on hands, you just need to bring him down by trying to use some of the same tactics.
And I would suggest dropping alchemy for engineering; currently alchemy has no benefit at all for you on these levels. Engineering has to many tricks up its sleeve for you to ignore.
just my 2cents; I must say that I do not play a warrior twink (or anything else besides a druid atm) so my advice is a bit based on field experience against and playing with warriors and from checking their abilities a bit on this level.