Here's a recent marth vs. puff, really sick match
http://www.youtube.com/watch?v=7Y5xAb_5GgQ
This is why stages are important; on bigger stages like dreamland, Marth's zoning tools become less effective because the size of the stage give the opponent more places to run to and it's harder for marth to cover, control, and capitalize on his opponent's options. For marth stage preference, I'd say Yoshi's is first, FD is second, FoD, battlefield, stadium, and then dreamland. Stadium can actually be a very good pick, but space animals will mess you up on the transformations. Winning the stages you pick is very important.
As for sheik, she's only a soft-counter to marth. The majority of Sheik's gameplay is about sneaking into your zoning range and wrecking your ****. Chaingrabs, tilts, just really nasty combos.
https://www.youtube.com/watch?v=kREm4Bsw58M . the MU is in sheik's favor, but watch how PP handles it: it's all about keeping sheik out.
It's hard to kill at high percents because after around 120% marth's moves don't combo into tippers or other killmove setups/situations. Ken combos are good gimps, but nothing beats a good edge guard. Never be afraid of wavedashing off the edge and grabbing it, very safe option, usually works. Dtilt, neutral B, and F smash also cover a lot of options. If you're feeling flashy, you can do a rising Dair from the ledge or even do 3rd hit of dancing blade down, which spikes.
For guarding Marth's recovery from off the stage, if they're not going to land on top of the stage (i.e. they are either going to sweetspot or end up near the ledge but not touching it) you can face away from the ledge and light shield, and before they can grab the ledge you will tumble off the side from shield stun and grab it.
As for counter, people will say what they will about its use, but I stand by it's judicious use. There are times when counter is not only your only option, but it is fact a very good option. Yes, missing a counter is a punish opportunity for your opponent, there is nothing more embarrassing than an empty counter. Bad counters and ruin a match, but good counters can save your skin. If you know your opponent is going to attack you no matter what, counter. Ken Vs PC chris, old school matches
https://www.youtube.com/watch?v=_fv2Z-ikYSg . Counter at high level play