I think that as long as a clear "mark of parody" is maintained such that a reasonable person could distinguish between the two, AI parodies are probably fine. The murkiness in my mind is expressly in the situation in the first episode of Black Mirror, where nobody could distinguish between the AI-generated video and the prime minister actually performing the act. Clearly that is not a parody, even if some people might find the situation humorous. But if we're not careful we give people making fake videos cover to hide behind fair use for parody.
I think you and I have the same concerns about balancing damage to the societal fabric against protecting honest speech.