Say I want to run a campaign where the PCs start as the Knights of King Arthur, the champions of the realm, as mighty warlords, and so on.
It really depends on the scope of the game you want to run. If you want the PCs to basically be defending (or holding together) a Kingdom for the whole campaign, you're looking at Heroic & Paragon. The playground is actually too small for Epic.
4e characters are functional from 1st level on, so that's not really an issue.
What do you think is the best starting level in standard 4e rules?
In general, 1st. A first level character doesn't have to be inexperienced, in fact, given the things even first level adventurers can do, it'd be quite reasonable for them to be seasoned veterans, full knights and the like. That's a change from earlier eds with 'name levels' and 'late blooming builds,' that pigeon holed 1st level characters as rank amatures.
It seems to me that while higher = more powerful, complexity increases at higher level; in particular Paragon tier brings in more bells & whistles. And starting lower gives more space to grow.
Very true. Unless your players have a lot of experience with Paragon, you probably don't want to start a game at that tier. Heroic works a lot better.
It seems to me that is probably too low for a "you are established major heroes" feel, though. What do you think?
"In the land of the blind, the one-eyed man is King." The heroes are as major as the NPCs they're protecting are minor. Gaining levels is supposed to show growth, though. What sorts of threats do you want the heroes overcoming when the campaign starts? What sort do you have in mind for them to face as it's wrapping up?
Another thing to consider is that while gaining levels is a cornerstone of D&D, it's not exactly a cornerstone of fantasy fiction or myth. If you want the PCs to face about the same 'level' threats throughout the story arc of a campaign, you may not need to give out a lot of experience or have them gain many (or any) levels. You could have them gain treasure and re-training opportunities instead of experience, for instance, and have them be a convenient level - like 10th - the whole campaign. Radical, I know, but such options are open to you if you want.
I have a follow-up question re starting at Paragon - given that Paragon is more complicated than Heroic, if running a campaign for less experienced players, how should the DM deal with that?
Have them spend a long time at 11th, until they finally get to know their characters. Give them lots of opportunities to re-train - maybe even at ever extended rest, so they can get the character into the shape they'll be comfortable playing. If you want to do that without restricting experience, that'd mean a lot of underlevelled encounters - which would further establish them as relatively 'mighty.' Maybe bandits or orcs or whatever fits your campaign.
What approach should I take to sources for PC generation?
If you want to restrict it, I'd do it by source - which also gives your campaign a definite feel. For an Authurian feel, for instance, you could have the PCs be primarily Martial, with Divine a possibility for one or two at most (probably a Paladin), and things arcane left to the NPCs and bad guys.
Would it be better to eg restrict characters to Essentials, or does the game need to be broader for long term play, eg you need to choose a Paragon Path at 11th, so should a wide variety of Paragon paths be available at chargen?
Essentials is OK at low heroic, but gives very little choice or customization (which is ideal for completely new players or returning AD&Ders starting at 1st level). If you really are thinking of the players being 'knights' of the kingdom, for instance, the Knight class does not deliver a lot of unique character options. A party of Fighers and Warlords of different builds, OTOH, could be quite varied.