1. Defeat Lord Harke.
Elwin starts right outside your starting town, but he hasn't officially visited it yet. So if Elwin has nobility, bring up the town's information screen so Elwin gets set as governor. Then move him straight west towards Gramin. Once he gets close enough, Gramin will be able to move (he's stuck otherwise).
Gramin starts out level 25, but he can't do much on his own because most of his skills are tactics skills. So you can try leaving the two heroes in their own armies so they cover more ground, but it's probably best to put them in an army together.
Note: Elwin starts out with the Bow of the Elf King, which gives ranged units an extra shot. That, obviously, makes ranged units much more powerful, and so you might want to skip water elementals this scenario and rely exclusively on fire elementals.
So start exploring. Right next to your town you'll find a quest hut plus a three-way portal leading to a crystal mine and a small treasure area. The inhabitant of the quest hut will give you a "pot-o-gold" if you return his Four Leaf Clover to him. (The pot-o-gold is about 8000 gold, not an artifact.) His "arch enemy" is the stack of leprechauns at the end of the Ungthor's Path choice in the portal. Try to do the quest right away since it will make building up your town easier.
Also notice the red dragon portal exit near your town. There are no less than four such exits in your area of the map. Plus, there are two red dragon portal entrances in Red's lands (which you can't get to), and Red's lands aren't very large, so you'll be seeing Red's heroes using the portals all throughout the scenario. If Elwin is so powerful that you don't need Gramin to help him, then just stash Gramin in your starting town, and use him to hunt Red heroes. After the first one (or two), which will be around level 27, all the Red heroes will be level 1, and they should be easy to defeat.
So, for that first Red army, use Elwin in the battle, and have him summon phoenixes every turn. Then have the phoenixes attack the enemy heroes while the enemy troops all attack the phoenixes. Once the heroes are dead, it'll just be a case of mopping up.
Otherwise, try to explore your area of the map as quickly as possible. South of your starting town you'll find two neutral Nature towns that should be easy to capture. South of that lies Teal's (Harke's) lands, but there is a group of behemoths and cyclopes blocking the way, so you're safe enough from Teal for a while. North of your starting town you'll find another neutral Nature town, plus a multi-way portal leading to a few treasure areas. (The treasure areas contain a lot of skill shrines if you need them.) So explore as much of the northern area as you want, or until Blue starts knocking on your door, and then head south.
Once you're ready to confront Harke, purchase as many troops as possible and put them and both your heroes into a single army. Harke's army will be tougher than the end-scenario armies you've seen before, mostly because he seems to accumulate all the troops from all of Teal's towns. Harke is also level 39, plus a tactics specialist, so his army will be even more difficult than normal.
So when you face him, start summoning and try to kill him first so you can get rid of his tactics bonuses. This is the last major battle you'll face in the campaign (everything else Elwin can handle all by himself), so don't worry about losses. Just make sure Elwin survives and you defeat Harke's army (Gramin doesn't need to survive). If you have trouble, capture the first two Teal towns you come across (one might still be neutral), and then just blockade Harke until you can defeat him.
Once Harke is defeated, go through the quest gate at (197,107) (northeast of Teal's southwestern town). You'll find the red keymaster tent there, which you can skip, plus a teal dragon portal, which you should take. The portal will take you to a blue keymaster tent and a purple dragon portal. Visit the tent and then take the purple portal, and then walk all the way back to the coast near your starting town.
You'll find the blue keymaster gate there, plus a blue boat waiting behind it. (You remember the introductory story about blue sails and red sails, right?) So board the blue boat and sail to the island where Shaera is waiting. Then just walk up to Shaera to win the scenario (and the campaign).