Super Mario 64/Wing Mario Over the Rainbow

In the room with the Tick Tock Clock level, go to the left and enter the hole in the wall. Collect the eight red coins in this level. This is one of the hardest stars in the game. If you fall down from this level you will not lose a life; instead, you will end up outside the castle in the lake.

Super Mario 64 DS

The second star is much easier. You need Wario though. Go to the cloud with the cannon, the tree, the pink bob-omb and the black bricks. Break the black bricks to achieve a star.

You have to collect all 8 red coins with a winged cap. There are 2 cannons to assist you.

1. Once you start off, do a complete 180 to find a coin directly behind you.
2. Find a pink platform nearby and land on it. Grab the wing cap and follow the rainbow to a cloud for the second coin.
3. To the left will be another pink platform with a pink Bob-Omb. Grab the coin here and open the cannons.
4. Jump in the cannon and aim it at a cloud that has many rainbows connecting to it, next to a blue cloud. Aim a little higher than these and shoot yourself to the cloud for the fourth coin.
5. Head back into the cannon you just came from. Turn left and aim yourself above the next pink platform and shoot to land on it. Jump into the cannon here and aim above the blue cloud you saw before. You should fly right through it, grabbing the fifth coin in the process.
6. Maneuver to the left and grab the green poles hanging off of a cloud. The sixth coin is here.
7. Slide down and drop off the pole. Near you is another cannon. Jump in and aim above the cloud with the poles. Shoot yourself off and you'll find the last two coins.

Make sure you always replenish your wing cap when you can, so that you don't lose it in the middle of flying around.