I used to really care about the idea that Paul was a Herodian, but not anymore. I don't see how it would change anything if he was. Herod's family converted to Judaism and that made them Jewish, and if Paul was part of that family, then he was Jewish too.
Herod's Jewishness only becomes "complicated" (as this article concludes:
https://www.thetorah.com/article/how-jewish-was-herod) if you make it so. And even if you make it complicated, Herod still sounds "Jewish enough" to me, and the article notes evidence for Herodian observance of kashrut and ritual purity. For example:
The King of Judea and his revered guests enjoyed delicacies such as Italian apples and Spanish garum, which is a fermented fish sauce used as a condiment. Scientists who studied these containers of garum determined that Herod’s was an unusual blend, containing only kosher fish, in contrast to the usual recipe. This shows that the people exporting garum to Herod knew about this Jewish prohibition and assumed (or were told explicitly) that Herod followed it, and that he was willing to pay extra for this.
Herodians may not have been "Jewish enough" for some, but they were for others (and to me). M. Sot. 7:8 is a good example of this.
King Agrippa stood and received it [the Torah] and read standing, and the sages praised him. When he reached, “You shall not place a foreigner over you” his eyes ran with tears.
They said to him, “Fear not, Agrippas, you are our brother, you are our brother!”
https://www.sefaria.org/English_Explana ... l&lang2=en
As noted in the link about this passage:
Some commentators say that the sages just said this to make him feel better, while others say that since his mother is an Israelite, he is indeed a legitimate king.
So was Paul "Jewish enough" (assuming he was a Herodian)? I don't see why not. Is it a "complicated" issue? Not to me.