The simple past, as in "I saw her" or "Did you see her?", generally implies a specific time, or inside a specific time-range that ends before the present. For example, I might say, "I was looking for her all of yesterday, but I didn't see her." This means that I didn't see her yesterday — but it doesn't say anything about whether I've seen her today. The following sentence could easily be, "So I guess she must have left town; I don't know if I'll ever see her again", or it could just as easily be, "But then I ran into her five times today, when it was already too late to invite her."
By contrast, the present perfect, as in "I've seen her" or "Have you seen her?", implies that the time-range of interest ends at the present. For example, one might say "I've been looking for her all day, but I haven't seen her."
It is possible to have two sentences that are identical except for this distinction, in which case the verb form conveys an important nuance of meaning. "I didn't see her today" implies that "today" has finished in some way — perhaps she is a coworker, and what I mean is that I didn't see her at work today, even if it's possible that I might run into her at the grocery store in the evening — whereas "I haven't seen her today" implies that there's still a chance that I will see her later today.
In your example, however, I would say that only "I'm looking for Paula. Have you seen her?" is acceptable. I cannot think of a context where "I'm looking for Paula. Did you see her?" would make sense. "Did you see her?" implies that you are referring to some specific past time or some specific past time-range; but since it doesn't explicitly indicate the time-range, that must be inferred from context. The problem is that the previous sentence, "I'm looking for Paula", implies that the time-range of interest is now, and the "did" version must end before now, so it's not compatible. As a result, saying "I'm looking for Paula. Did you see her?" makes about as much sense as "I'm looking for her. Have you seen him?" — the second part must be referring back to something, but it clearly can't be referring back to the first part, so the whole thing comes out sounding like gibberish.