I'm not sure about DK being in the game, but Yoshi could definitely.
I like your idea about mixing powerups....It was the only thing I wished was in the past Marios. Anyways, I think levels should be playable with whatever power-up combinations, though a specific combination makes the level easier. Also, you didn't mention the frog suit or the boot. A level could consist of parts in which flying is useful, but all the sudden you head into water where the frog suit is useful. Towards the end of that particular level, an item for speed only would be useful because a gaint turtle shell chases you across the screen. Alternative methods should still be able to finish the level, but having the feather/frog suit/speed-item combination allows for it to be beat relatively easy. Clues could be given to what combination you need. Stars shouldn't be able to upgrade. They should still be temporary, and do not change the combination of power-ups you have at that point.
Warp Pipes should not just transport you to a different area (underground, bonus area), but it should warp you to previous Marios to bring back that nostalgic feeling. Imagine playing this new Mario 128, then after warping through a pipe, you end up playing bowser in the original NES version. A nice graphical cutscene of sorts should take place, maybe with Mario warping and transforming, you still don't know what he's going to end up looking like or what game he's from. Then he lands on the ground, a big cloud of dust covers him so you can't see him, then he appears as NES Mario. Once you defeat Bowser, you reap a bonus item (maybe a combination chooser, so you can pick exactly what 3 power-ups you want), or the beloved flute.
It'd be interesting to say the least if Nintendo went with something like this....nice speculation