Approximate computing is an energy-and power-efficient design paradigm for error-tolerant applications. To enable this paradigm, different techniques have been proposed across the entire computing stack. In isolation, these techniques have demonstrated sufficient savings while promising results at complete System-on-Chip and application level are expected. Since half a decade ago, the notion of cross-layer approximate computing has been around in the scientific community. However, to fully accomplish a synergistic use of approximate computing techniques at different levels, existing challenges need to be overcome. In this paper, we discuss key challenges required to be addressed by the scientific community, to unlock the full potential of cross-layer approximations to achieve the ultimate system-level optimizations for error-tolerant applications. We present a crosslayer methodology for designing approximate systems, in which we consider the joint use of existing approximate techniques and contemplate other required methods, such as, statistical analysis of error propagation across different approximate components, and error compensation through self-healing approximations that would enable high-efficiency gains at the system level without aggregating the error magnitudes.