Some can (see modern CPUs which have a huge chunk of them integrated into the package). It's likely to be quite expensive for most packaging processes and realistically for a lot of them there isn't really enough space. (on older style DIP packages there might be enough space for some of the modern smaller caps but the caps available at the time would not fit).

With on-die capacitance you can't realistically get enough capacitance for decoupling in the right frequency range (though it is still relevant: in practice decoupling is a case of multiple overlapping filters, from the response of the regulator itself, to any bulk capacitance, to local decoupling capacitors on the PCB, to the plane capacitance of the PCB itself, to the capacitance of the power distribution inside the IC. Each of these stages has a lower inductance but also a correspondingly lower capacitance and so deals with a higher-frequency part of the load).