It depends a lot on what you want to do, on how much time you have to do it, and on how much you wish it to be an acquired skill. I have worked for years with Sony Vegas, and with plenty of Adobe products having made de switch from Sony Vegas to Premiere a few years ago.
Sony Vegas is pretty good for some basic-advanced editing, it's definitely the most friendly software that will also help the average person get the best end result easily. For editing some holiday footage, some fun with friends, some birthday, in general averagely sized projects.
AfterEffects is not for editing, it is for motion graphics/special effects, and indeed most of that third video was probably created on After Effects. It takes a good amount of time to master After effects, and to create those kinds of animations you will very likely need to use photoshop as well.
Premiere is for advanced editing, and is likely the best, most professional option you have on a PC. However its main flaws is how unintuitive and clumsy it can be for beginners. It's still a bit of a pain for me to use premiere nowadays for certain things. If you want to do a larger project (or want to do one in the future), then you better start learning premire now. I handles larger projects better than Sony Vegas, allows you to do more complex things, allows you to have better color correction, allows you to have a connected workflow between adobe software, better quality output... (I finally snapped for the switch after Sony vegas started to crash and become corrupt when I was handling a long (30mins) film with a lot of edits, had to edit everything again)
If you want to have pretty good results with less frustrations and quicker/faster learning and editing times, go with Sony Vegas. That first video could have easily been done there.
If you truly want to have the best possible end quality results then start away to learn Premiere, I would say that second video could have been done using Premiere because of the quality color correction (even though it just seems to be a mash up cut from different sources)
Premier pro, Sony Vegas and after effects. The 3 and only 3 that you need in life if you are trying to be a pro.
Though why would someone choose to use and invest learning time and money in both Vegas and Premiere

?