Are there any PaaS where I can run AE? I have an app where we allow users to create videos by choosing an After Effects template and modifying the text, images, etc.
We run AE on a windows server which renders the final video.

For other scenarios where we do not use AE, we use AWS Lambda of which we can spin off 100 instances simultaneously and they all use their own resources. Whereas for AE we use a Windows server and all parallel rendering use the same resources and hence are very slow.

Are there any PaaS where I can run AE and spin up multiple instances?
There are no true PaaS providers for After Effects. However, there are several online render farms (SaaS).

Note that you cannot run After Effects on a public cloud in your own render farm.