I'm converting my numerous comments into an "answer" -- I don't currently know the exact species, but I can at least explain some of my thoughts more completely.
Your specimen looks a lot like Gonatista grisea, a tree mantis that mimics a lichen -- as you mention in your post. However, G. grisea, is native to the southeastern USA. I could find no evidence of any reports finding this species in Africa, so we will rule it out.
If we examine some other species of the Gonatista genus (e.g., G. jaiba, G. major, G. phryganoides, and G. reticulata) we find that they are all neotropical and not found in Africa. Therefore, let's look elsewhere.
So, I would recommend examining other close members in the same family that are found in Africa.
I originally recommended reviewing Patel et al (2016) because they provide a checklist of the global distribution of other members of the Liturgusidae family. Using this guide, we could examine known African genera.
- They list Dactylopteryx, Majanga (Madagascar), Theopompella, and Zouza as African genera.
However, I had not realized that there had been some taxonomic rearrangements, and Gonatista is now in the family Epaphroditidae.
The other genus in the same subfamily as Gonotista, Gonatistella, is monotypic, and G. nigropicta is not your species.
The other genera in this family, Epaphrodita and Callimantis, (as well as the now-moved genus Brancsikia) also do not seem to contain any species I could find that are morphologically similar to yours.
So maybe we should look elsewhere in the previous Liturgusidae...
Subtribe Humbertiellina in the Gonypetidae family are just one example of another group perhaps worth investigating because it too was once contained within the original Liturgusidae family along with Gonatista and because some online evidence suggests some members of this subtribe (e.g., Humbertiella and Theopompa) share some similar physical characteristics to Gonatista.
- Some non-reputable sources (e.g., here for Humbertiella and here and here for Theopompa servillei) show specimens similar to yours with labels as one of these two genera. I couldn't find consistent imagery or reputable sources with imagery to support either one as correct...
- (Also, Patel et al. (2016) suggest these genera are recognized as Asian genera, and so they may be geographically unlikely anyway like Gonatista).
However, perhaps trying to solve your unknown specimen using taxonomic and trait-similarity approaches could be misleading.
According to Rivera (2010): "Whereas the monophyly of Mantodea is well supported, the evolutionary relationships within the order are still contentious. Several classification systems for mantids have been proposed...However, the natural affinities among supraspecific taxa have been extremely difficult to discern due to the highly variable and derived morphology of these insects."
According to Schwarz & Roy (2019): "As already noticed by previous authors, external morphology is highly homoplastic and does not provide useful systematic tools above subfamily level."
Schwarz & Roy (2019) do suggest that the morphology of male external genitalia may be useful for relating individuals as these traits tend to be fairly congruent with more recent molecular phylogenies. You could start there for further research.
- (I myself can't discern meaningful detail of the genitalia in your photos, nor am I any type of expert on mantises, so this route of inquiry might be too much in the weeds for me...)
If you find a good key for your region, you might want to check out Brannoch et al (2017) for a "Manual of praying mantis morphology, nomenclature, and practices" to help you with all the mantid jargon. [it appears to be a very thorough and excellent resource!].
I will update this post if I find anything more definitive for you...
Brannoch, S.K., Wieland, F., Rivera, J., Klass, K.D., Béthoux, O. and Svenson, G.J., 2017. Manual of praying mantis morphology, nomenclature, and practices (Insecta, Mantodea). ZooKeys, (696), p.1.
Patel, S., Singh, G. and Singh, R., 2016. A checklist of global distribution of Liturgusidae and Thespidae (Mantodea: Dictyoptera). Journal of Entomology and Zoology Studies, 4(6), pp.793-803.
Rivera, J., 2010. A historical review of praying mantid taxonomy and systematics in the Neotropical Region: State of knowledge and recent advances (Insecta: Mantodea). Zootaxa, 2638(1), pp.44-64.
Schwarz, C.J. and Roy, R., 2019, March. The systematics of Mantodea revisited: an updated classification incorporating multiple data sources (Insecta: Dictyoptera). In Annales de la Société entomologique de France (NS) (Vol. 55, No. 2, pp. 101-196). Taylor & Francis.