Hard for me to say what it would take for a normal small dev team as I am a beneficiary/stakeholder of this work but wasn't involved in the development. In our case we hired a dedicated senior infra swe who had experience in building IaC and other automation. I think given our startup at the time (b-round startup working in healthcare with duck-taped infra and security) it was absolutely the right decision for us.

It took our infra swe a few months to get MVP version working but he also did other infra related work at the same time. Complexity can change a lot depending on requirements, and ours are probably more stringent that Heroku ever supported. Because of sensitivity of the data we deal with there is now a relatively sophisticated identity management/permissioning/what-can-see-what-data component in how our infra is deployed which probably would not be the case for most companies. We also deploy ML models so there is additional issues with automation around keeping track of reproducability/provenance/ml pipeline regression/drift/deidentification/etc (which now a year later we haven't fully solved either!).