You should do that when she came
You should have done it when she came
You should do that before she came
You should have done it before she came
You should do that after she came
You should have done it after she came
1 means that something should be done after her arrival and 2 before. Let's now consider 3 and 4. To me both are fine and mean the same thing. Now 5 and 6. I think 5 is okay but 6 I'm not sure about it.
To sum up: I'm sure that my understanding of 1 and 2 is correct. I don't know what about the rest. Can you tell me if they make sense?