This is exactly what PaaS's like Heroku have been doing for years, right? Isn't Lambda just an even more locked-in PaaS?

Heroku is a bit higher level. If you're using heroku, you're using their blocks and their methods of passing traffic, logging, etc. With lambda, it's just a function. You have to connect everything yourself, not you can do it exactly the way you want.

You can redeploy a Heroku app to many other servers and platforms relatively easily.

However, I'm not sure you can do the same with AWS Lamda Functions. To mean, this means it is like a lock-in.

It's just code with basic function entry point. You may get your parameters and configuration in a different way, but not much else changes. There are only so many ways to call some code.

And a huge plus - not having to pay if nothing is using it (generally).

The downside being that you pay a lot more if it gets used a lot.

Which is probably when you need to re-architect, anyway. There are also several optimizations that can be made along the way to reduce costs. I think there are plenty of ways to think of problems from a serverless standpoint that really don't need to go the traditional server route. I also think there are plenty of use cases where serverless may very well be a problem, that's okay.

Except for max run time limitations and recurring long startup times, sure. No free lunch.