In M-ary Aggregate Spread Pulse Modulation (M-ASPM) [Nikitin, A. V. and Davidchack, R. L. (2022) IEEE Access, 10 96652-96671], while an entire transmitted packet can consist of constant-envelope pulses with the same magnitude, different segments of the packet can employ considerably distinct processing gains, and have significantly different sensitivities to the carrier frequency offset (CFO) between the transmitter and the receiver. Thus a relatively short, low-gain front portion of the packet that is insensitive to a large CFO can be used for robust asynchronous detection of the packet at low computational cost. Further, this detection can be combined with measuring the CFO within the desired range and with desired precision. Then the subsequent costly processing of the high-gain, CFO-sensitive segments of the packet (e.g., those allocated to the synchronization and the payload) needs to be implemented only after the detection, and can be performed without undue deterioration in the quality of the received signal due to the CFO. However, since the contrast in the processing gains between different portions of the packet can exceed two orders of magnitude, matching the detection sensitivity with that of the synchronization and decoding of the payload, while maintaining the portion of the packet dedicated to the detection relatively small, represents a significant challenge. The main objective of this paper is to provide a comprehensive description of the detection algorithm that meets this challenge, together with detailed explanation of the procedures and the tools employed in implementation of its steps.