You think it's impossible! Not really. Here is how to accomplish this. Short and sweet.

1. QAs are involved in pointing the stories. You decide in sprint planning/refinement if any automation needs to be done on the story. Everyone including QAs know the effort it's going to take. So, you point them keeping that in mind. And, you mention that as an acceptance criteria that automation needs to be done.
2. Technically for all new features you should be writing E2E testing and if so you don't need a different regression suit because one suit can be run on a regular basis(through CI).
3. "because the areas of testing and steps often encompass new domains and complicated environment setups": You shouldn't be writing any automation tests that cannot be fully automated. So, this scenario keep only manual and create documentations. And, I forgot to mention, when you write automation that's your test plans, no need to write manual tests plans and you concentrate fully on automation for that feature. There are plenty of ways to generate reports through tool.
4. QA cannot have a backseat: Because there is technically no designated role in Agile as QA. All of them are team members and if stories are becoming heavier in QA lane then Devs have to step up and clear the QA lane. And, if you push the stories out without giving QA enough time or QA cannot finish them and you want them to be out, there is of course something wrong with story pointing. They are not pointed right.
5. Choose an automation tool and language which go with the application architecture. Such as select Java dependent tool(Selenium with Java) if you are a Java shop so that if QA falls behind Dev can easily pick up and finish, re-patch or write some automation tests cases. This scenarios will also cover the improvement of QA's automation skills since they can easily take help from devs for writing code and such. It dramatically speed up the process.

You think it's impossible! Not really. Here is how to accomplish this. Short and sweet.

1. QAs are involved in pointing the stories. You decide in sprint planning/refinement if any automation needs to be done on the story. Everyone including QAs know the effort it's going to take. So, you point them keeping that in mind. And, you mention that as an acceptance criteria that automation needs to be done.
2. Technically for all new features you should be writing E2E testing and if so you don't need a different regression suit because one suit can be run on a regular basis(through CI).
3. "because the areas of testing and steps often encompass new domains and complicated environment setups": You shouldn't be writing any automation tests that cannot be fully automated. So, this scenario keep only manual and create documentations. And, I forgot to mention, when you write automation that's your test plans, no need to write manual tests plans and you concentrate fully on automation for that feature. There are plenty of ways to generate reports through tool.
4. QA cannot have a backseat: Because there is technically no designated role in Agile as QA. All of them are team members and if stories are becoming heavier in QA lane then Devs have to step up and clear the QA lane. And, if you push the stories out without giving QA enough time or QA cannot finish them and you want them to be out, there is, of course something wrong with story pointing. They are not pointed right.
5. Choose an automation tool and language which go with the application architecture. Such as select Java dependent tool(Selenium with Java) if you are a Java shop so that if QA falls behind Dev can easily pick up and finish, re-patch or write some automation tests cases. This scenarios will also cover the improvement of QA's automation skills since they can easily take help from devs for writing code and such. It dramatically speed up the process.

Edit: Make sure the proportion of QA and Devs are right otherwise QA will always be behind because sometimes writing automation is heavier than writing application.