Maybe some kind of Christianity, but really if you have the required territory, you can pretty much claim whatever title you want. It doesn't really matter what religion you are in the end, at least in my opinion; that's what makes sandbox simulators fun.
I mean, if you hold the territory, and have the correct culture, why shouldn't you be able to claim the title? If I held all the French territory, and had French culture, should I be unable to form France if I'm not a Catholic? The rule is arbitrary at best, and if I wanna be a Sunni kingdom of Jerusalem, why not? It's a historical-flavored sandbox. And again, "Modern". The crusaders at the time knew they were in control of the Eastern Empire, and essentially functioned as the ruling dynasty, so why should we be prisoners of modern nomenclature for no particular reason? This argument also doesn't dismiss or counter my points on Prussia.
And this is obfuscation. It doesn't matter about the political system or mechanics, as you can form Germany or Britain as a republic. What matters is there's a title you can claim, and as a Prussian state was formed by a Catholic monarchy, it demonstrates that a Catholic nation can technically form Prussia, and argues against a Protestant requirement.
And while it might be fair to say that, the fact is we can argue mechanically this means that the state can have the option of Protestantism, but not the requirement for its formation.
And they could crown themselves in "King in Prussia", not "King of Prussia". To be very reductive, it was politics; there could legally only be one King in the HRE, which was Bohemia. And Prussia was technically legally a vassal of Poland, so you couldn't declare yourself King of Prussia without pissing them off, until Poland got beat up enough. This situation really only applies to Brandenburg, and only if one strictly models history, which is unlikely to happen in most games. Plus, if I'm a tag outside of the HRE, and able to beat up Poland, there's no legal or political reason I shouldn't be able to claim I am the king of Prussia. But if I am in the HRE, choose to remain Catholic, and choose to elevate myself to the Kingdom of Prussia, I should perhaps be required to play politics with the Pope and Emperor to make that happen legally, or risk an Imperial Ban and lose the protection of the Empire. At least that would be fun.