Carbon capture and storage (CCS) in underground structures depends on the quality of the geological reservoirs. Factors including interconnectivity in the pore spaces, natural fractures, reservoir thicknesses/depths, preexisting fluid (water or hydrocarbon), traps, and overburden integrity express the CO2 storage potentials of the geological reservoirs. This study presents the CO2 storage efficiency factors considering the associated geological parameters involving basalt, shale, carbonate, and siltstone. It evaluates the basalt–sedimentary rock interactions and their impact on the complex, heterogeneous, and unconventional reservoir systems in the Paraná Basin concerning CO2 storage. It considers the reservoir porosity, thickness, and area for CO2 storage with the associated uncertainties based on the efficiency factors EΦ, Eh, and Ea, respectively, to propose the algorithm for capacity estimation. Including water saturation and water salinity-based efficiency parameter in the CO2 storage capacity estimation expression depends on the percentage of water in the reservoirs and water salinity. Each rock unit has its limitations concerning CO2 storage; however, the potentials for CO2 repositioning abound. Based on the storage efficiency parameters, the suggested reservoir options include the basalts and the hybrid geological reservoir of the Irati Formation, considering the shale–carbonate reservoir, the shale–siltstone reservoir, the carbonate–siltstone reservoir, and the shale–carbonate–siltstone reservoir. Reservoir options within the Rio Bonito Formation could include sandstone and the sandstone–siltstone hybrid. The hybrid reservoir option may increase the CO2 repositioning capacities by reducing some of the input parameters’ associated limitations. Prospects for CO2 injection wells and storage site monitoring and leakage detection abound, considering existing related programs in Brazil and the proximity of well-equipped institutions with the technical know-how. The Research Centre for Greenhouse Gas Innovation in the Polytechnic School and the Institute of Energy and Environment of the University of São Paulo have shown keen interest in CCS-related research. No hydrocarbon production data sets are yet associated with the study area; therefore, the findings provide the basis for estimating the CO2 storage capacity associated with the rock units. Furthermore, detailed studies involving water saturation and salinity of the reservoir water are pertinent to choosing the suitable expression to predict the CO2 storage capacity of Irati and Rio Bonito Formations.