The typical mainstream CPU might have 16 PCI-E lanes but you're discounting the lanes that come from the chipset. For instance, The Intel z390 chipset has 24x PCI-E 3.0 lanes.
This is the reason I STRONGLY recommend avoiding entry level chipsets like h110, h310, and AMD's a320. In sharp contrast to the z390 chipset, the h310 chipset come with 6x PCI-E 2.0 lanes. At the bare minimum, if you're going with Intel then go with the b360 chipset because it has 12x PCI-E 3.0 lanes.
Yes, there are both SATA based and PCI-E/NVMe based M.2 drives. M.2 is merely a form factor and an interface. The most common PCI-E/NVMe drives like the Samsung 970 Evo series uses 4x PCI-E lanes but it should use the lanes that come from the chipset and not the CPU. No need to worry about cutting into the CPU's limited PCI-E lane allotment.