Super Mario World/Star World 1

By spin jumping along the right edge of the level you will be able to reach the key easily. A Baby Red Yoshi is found in the bottom portion of the level, but it's hard to get, and will need a bit too much food. I really think you should use Star World 4 if you want Red.