Most are correct, but with slightly different meanings. Rough paraphrases might be.
1. Did you notice (at a point in past time) his staring at at you (an action that had begun before that point and probably continued up to that point)?
2. Did you notice (at a point in past time) his staring at you (at that point)?
2.[your second 2] Did you notice (at a point in past time) his staring at you (an action that had begun before that time and continued after it)?
3. This is unlikely if the staring is happening at the moment the question is asked ([5] is more likely). However, it's just about possible if the context is something like: Whenever I see him, he is always staring at you (the staring began before I see him, and continues throught my seeing him). Do you notice this (i.e. on those accasions I am talking about)?
In [4] and [5], have you noticed implies that the possibility for you to notice began in the past and is still present. In both cases the staring is going on at the moment of speaking, but in [4] the speaker is emphasising the duration of the staring - it began in the past and continued up to, and through, the present moment.
I suspect that Americans might well use did you notice in [4] and [5]