Tu problema se debe a que pones el panel de dibujo en la parte derecha de BorderLayout, y como no tiene tamaño ya que no hay componentes dentro de éste, no puedes obsevar el rectangulo dibujado. O le das un ancho al panel de dibujo o lo pones en la posición del centro (BorderLayout.CENTER).
En el código que pones no inicializas el rightPanel y le agregas el panelDibujo a éste cuando no es necesario ya que puedes agregarlo directamente en la posición que elegiste (EAST o CENTER).
Además, no es recomendable agregar los componentes directamente sobre el JFrame, éste te devulve un Container (en este caso un JPanel) con el método getContentPane() para colocar los componentes ahí.

A continuación te dejo el código que me funciona.
El problema está en los layout, debes de fijarte bien cómo funcionan. Estos son los encargados de colocar los componentes y dimensionarlos. En el caso de BorderLayout, que ya lo sabrás, coloca los componentes en NORTE, SUR, ESTE, OESTE y CENTRO.
Cuando coloca los componentes, por ejemplo, este u oeste, se fija en su ancho porque del alto se encargará de ajustarlo el layout. Utiliza setPreferredSize() para establecer el ancho; el alto en este caso no importa, puedes dejarlo a 0. También quité el rightPanel y ahora se agrega en la posición derecha (EAST) directamente el panelDibujo.

Por lo de getContentPane(), como dije, devuelve el Container (en concreto un JPanel) que es mejor utilizar para colocar los componentes en lugar de agregarlos directamente sobre el JFRAME.

import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.JButton;
import javax.swing.JTextField;
import java.awt.GridLayout;
import java.awt.BorderLayout;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Color;
import java.awt.geom.Rectangle2D;

public class veintitres extends JFrame {

private JPanel leftPanel, rightPanel;
private JButton menu[];
private final String nombres[] = { "Pluma ON", "Pluma OFF", "Avanzar", "Girar Derecha", "Girar Izquierda" };
private JTextField pasos;

public veintitres()

{

super("veintitres");

// CREACION DE LOS PANELES
// ==========================================================

getContentPane().setLayout(new BorderLayout());

leftPanel = new JPanel();

leftPanel.setLayout(new GridLayout(5, 1));

/*
* ELIMINÉ EL RIGHT PANEL
*/

menu = new JButton[5];

for (int i = 0; i < nombres.length; i++)

{

menu[i] = new JButton(nombres[i]);

// menu[i].addActionListener(this);

leftPanel.add(menu[i]);

}

pasos = new JTextField();

pasos.setPreferredSize(new Dimension(20, 20));

leftPanel.add(pasos);

// ---------clase anonima para poder dibujarlo en rightPanel

class panelDibujo extends JPanel

{
@Override
public void paintComponent(Graphics g)

{
//super.paintComponent(g);
System.out.println("dib");
Graphics2D g2D = (Graphics2D) g;

g2D.setColor(Color.RED);

g2D.fill(new Rectangle2D.Double(10, 10, 200, 200));

}

}// fin class

panelDibujo panelDibujo = new panelDibujo(); // creamos el objeto
panelDibujo.setPreferredSize(new Dimension(300, 0));

setLayout(new BorderLayout());

getContentPane().add(leftPanel, BorderLayout.WEST);

getContentPane().add(panelDibujo, BorderLayout.EAST); // USA MEJOR CENTER!!!
}

public static void main(String[] args) {
veintitres VEINTITRES = new veintitres();
VEINTITRES.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
VEINTITRES.setSize(800,500);VEINTITRES.setVisible(true);
}
}

Por cierto, otra cosa que tener en cuanta es cómo funcionan los layouts: cada vez que una venta o un componente necesita organizarse, como cuando cambia de tamaño, se llama al layout para que este organize los componentes en función del tipo que de layout que sea, los parametros con el que se crea y los demás componentes. El método setSize que utilizaste no funcionó porque es el layout el encargado de establecer el tamaño, pero puedes utilizar setPreferredSize ya que lo toma en cuenta el layout. Pero todo depende del Layout que utilices.
Piensa, por ejemplo, que a un componente le pones como layout null y todos los componentes que contiene les estableces unas posiciones y dimensiones (con setSize, ahora sí). Cuando Swing se encargue de pintar los componentes, los dibujará en estas posiciones ya que ningún layout modificó sus medidas.
Pero, como dije, va a depender del layout que utilices; unos te dejarán ajustar alguna parte con setPreferredSize como el caso del ancho BorderLayout.WEST o BorderLayout.EAST y otros no como GridLayout.