I have published a paper in a fake journal. I want to withdraw the paper from that journal.
Can I can submit the same paper on a legitimate journal, after withdrawal?
I see two main barriers for this to happen, and I would not attempt to cross either unless ths circumstances were truly exceptional.
The worst case scenario is one where the paper is very visibly retracted, you do not get the copyright back, and you cannot republish it anywhere. I can't really imagine any degree of shadiness of the original journal that would make this outcome preferable, because a retraction will leave a very visible, very black mark on your publication record for a long time. As mentioned in the comments, retractions are vivid indications of academic misconduct, plagiarism, or just plainly incorrect findings, and rarely of anything else. Therefore, you should be really careful that this doesn't happen.
I would advise you to take this in stages. First, read all the documentation you have available. Read very carefully, in particular, anything you have signed, either in paper or electronically, to the original journal. Check all their publicly available policies, and particularly those on licenses and copyright. Check also what your new target journal states as their requirements that submissions be 'new, unpublished work'.
Armed with this information, contact your new target journal first, to see if they will re-house your paper after it's been withdrawn, and what conditions they would require for this. Do not move forward until you have good assurances of a good home for your paper, or you risk ending up with a homeless paper.
After that, you should contact the original journal. If you gave them the copyright, you will have to ask for it back but you should be prepared for them to say a plain no. I suppose that if you gave them a more restrictive license then you can ask that they take it down and find out how you can revoke it, but you should be aware that author contracts do not normally include anything like that. Be polite and explain why you are doing things but be prepared for things to turn adversarial; you are after all out to affect their revenue stream.
Mostly, though, why don't you consider your options in terms of fixing the damage this publication has done to your record? Publishing in a predatory journal without knowing it is something that can end up happening to anyone (which is why one should always exercise maximum care when opting for a new publication venue).
Keep in mind that the venue of publication does not affect the quality of your paper, but only (potentially) how it is perceived by others. This can be palliated by other means: for example, take the paper to conferences and explain and defend your findings to your peers. Work especially hard at making sure the material finds its way to the hands of people who will use it and cite it, and that will help validate it as good research in a possibly shady journal.
If the journal is not very visible or accessible, post it to an eprint repository if it is possible (though of course only if other republication options are exhausted and allowed by your original journal, or if you are prepared for your relation with them to turn adversarial). Consider building a bigger paper, formally a derivative work, which you can then publish in a journal you're happier with.
In short, there are many options available to mitigate the damage done by a paper in a journal you (and whatever review boards you might come across) don't like. Think them through before you attempt something which is as potentially damaging as this.