They seem to have omitted most of the Proteobacteria for which 16S sequences are known, probably because there are so many. But those would include the organisms you mention.
I was under the impression that cyanobacteria had been assigned their own separate kingdom.
The paper suggests an origin of kaiB 2300 million years ago. That would be after the cyanobacteria diverged from the others, which don't have kaiB. So the cyanobacteria have had a separate lineage for around 2.5 by, which is old enough to give them a kingdom, IMHO.
I remember going over the origins of life exhibit at the Smithsonian Natural History Museum ("Elephant Building" to us natives). Thirty years ago, I only wanted to look at the dinosaurs of course. The study of microfossils is a fascinating subject that it seems no scientists can really agree on. Fossil stromatolites and algal mats are undeniable but it seems one can never be quite sure if itty-bitty dot-structures in a slice of shale or chert qualify as life or mineral grains.