Ultra-dense 3D ICs, with ultra-dense 3D connections (pitch < 100 nm), are projected to achieve large energy and throughput benefits compared to today's ICs. To enable many high-power compute engines on 3D tiers, 3D thermal and power delivery challenges must be overcome. We use a recent idea called 3D thermal scaffolding to overcome both challenges simultaneously. 3D thermal scaffolding cools ultra-dense 3D ICs (e.g., monolithic 3D ICs) using a combination of (1) a new thermally conductive dielectric (the 'thermal dielectric'), (2) scaffolding vias for heat conduction paths to the heat sink, and (3) efficient (and experimentally demonstrated) heatsinks. In this paper, we present new algorithms which place scaffolding vias and the thermal dielectric with minimal footprint impact while satisfying peak temperature and worst-case IR drop constraints. These algorithms are implemented during physical design and demonstrated using a 12-tier open-source 7nm AI accelerator design. Compared to approaches that do not consider power delivery and thermal constraints simultaneously, our approach reduces the footprint penalty due to 3D thermal scaffolding from 10% to 5.5%-an 80% improvement-and simultaneously meets worst-case IR drop constraint of <20 mV at 0.7V supply and peak temperature constraint of <125℃.