Scusa ma provieni dal Visual Basic 6? Il fatto che la procedura si chiami Button_Click non implica che venga eseguita quando si fa click sul pulsante: solo la clausola Handles conta davvero per il compilatore. Fidati, se scrivi e.Graphics.qualcosa in paint funziona, ho provato io:
codice:
Private Sub Form1_Paint(ByVal sender As System.Object, ByVal e As System.Windows.Forms.PaintEventArgs) Handles MyBase.Paint
    e.Graphics.FillRectangle(Brushes.Blue, New RectangleF(100, 100, 100, 100))
End Sub
produce questo risultato: