Story: Storywise, I don't think there's anything wrong with it, though I'm not sure what this "other world" Mario lives in is since the explanation of the plot was fairly brief. But, the idea of having a robot destroy the creator in pursuit of power is something fairly new for a Mario hack, and I would encourage you to continue using it.
S1: Nothing seems wrong with the first screenshot.
S2: Overworld is fine for the most part, except near the door, you have some grass that gets cutoff when you see it against the cliff, but it's over such a small area that it should be very quick and easy to fix.
S3: In the third screenshot, you have a bad corner tile near the lava - the corner has dirt behind it when it should have air. If you place the correct corners out of Direct Map16 Access, they won't be changed by objects you dragged underneath it in Lunar Magic. You can edit the pipe's graphics to make them fill their space so you don't have some air between the tar and the pipe as well, in GFX14. The palette has a very minor issue with the grass that can be easily corrected - just make the green furthest to the left darker so that the grass is properly shaded.
Video: Immediately I am concerned because you are starting off a level with a green baby Yoshi. The thing is, if you were to re-enter the level with an adult Yoshi, its head would glitch and look like the baby Yoshi. To fix this the easy way without it changing your plan, you will either want to disable Yoshi from entering (if the index has a rope, castle, or ghost house setting, you can use a No-Yoshi Intro) OR the other simple way would be to replace the baby Yoshi with an egg so it will check to see if Yoshi is in the level before it hatches. If it is, it will not yield a baby Yoshi, so the glitch will not occur. The downside to this is that you have a Yoshi with a special ability this early in the game: I'd recommend using the either the Yellow or Red Yoshi eggs if you're going with the latter plan, and avoid using the Blue Yoshi this early.
At :14, you see the bottom row being used to walk on. I'd move those (and the music blocks) up one tile because otherwise, you are only able to see one pixel of the cement blocks - making it difficult for many players to judge whether or not that is safe. Also, I would remove those coins from that part because as others have pointed out, it does make solid tiles in place of the coins.
At :28, there are some cutoff vines. Another really easy fix - just make them go up a little bit more so that if you climbed to the top and hit some kind of wall, you would still be able to reach the clouds, then connect the top of the vine to a cement block or something so they look like they are hanging from above.
Other than that, there's nothing really wrong with it, but there are some sections that could use a bit of cleanup:
A.) The area where you run up a slope, then the bullets go above you - they present little threat because of their placing, so I'd only keep the lowest bullet in and remove the unnecessary ones.
B.) The pipe section seems dragged on, and I noticed you didn't use any tileset specific sprites, so maybe you could use Super GFX Bypass and select different SP3 and 4 graphics for use with those, and have some things like falling platforms in place of the pipes to break it up a little. Variety is key in level design.
Good luck, in any case. You're off to a decent start.
Just look above you...
If it's something that can be stopped, then just try to stop it!