Here are two very good gearing guides:
The frost emblem guide I like (although I value the skeleton key a lot higher than Vene does, I'd put it around 7, and use cash for the pillars of might instead of emblems of frost):
As far as gemming/enchanting goes, check the link in my sig. Gemming and enchanting is pretty much the same for paladins and warriors.
If you want any more specific advice or don't understand something in the links, then respond and I will be more than happy to answer specific questions.
In general though, no you are not ready for ICC10 yet, however there are some crafted items you can make, some pieces of gear that are decently easy to get, and a gemming/enchanting overhaul away from being ICC10 ready.
And yes, gemming for stam is the right course of action.
Edit: And if you really want me to I can go over piece by piece what you should change, but I don't have time to do that right now, I probably could tomorrow though.