The differences you observed between Excel 2016 and Microsoft 365 for Excel are normal. Microsoft removed the "Paste and Match Destination Formatting" shortcut after the Excel 2019 update. Frankly, I don't understand why they made this change either. As a member of the support team, I do not have the authority to participate in the design and development of Excel. I can only share alternative solutions that I know of, hoping they will meet your needs.
- Method 1: After opening the Excel application, go to File > Options > Quick Access Toolbar > Choose commands from and select Home Tab. Scroll down to find Paste, select it, and add it to the Quick Access Toolbar. Click OK to save the settings.

At this point, this option will appear at the very top of the Excel application. Press and hold ALT to enter the quick action mode. Observe the shortcut key for the paste option; in my case, it is 5.
[
Now, press CTRL + V to normally paste your text into other cells.
Select cell A1 > Home tab > Format Painter. The cursor will turn into a brush. Select the unformatted text you just pasted into Excel to quickly apply the existing format to the unformatted cells.

I hope you find these alternative methods effective.
Thomas