Mac OS X captures C-M-d before it gets to Emacs. With the following KeyRemap4MacBook you can reclaim that keybinding and get your paredit-mode working.

private.xml

<?xml version="1.0"?>
<root>
  <item>
    <name>My Emacs tweaks</name>
    <item>
      <name>Enable Control_L+Command_L+D on Emacs</name>
      <identifier>private.emacs.enable_control_meta_d</identifier>
      <only>EMACS</only>
      <autogen>
        --KeyToKey--
        KeyCode::D, ModifierFlag::CONTROL_L | ModifierFlag::COMMAND_L,
        KeyCode::D, ModifierFlag::CONTROL_L | ModifierFlag::COMMAND_L | ModifierFlag::SHIFT_L
      </autogen>
    </item>
  </item>
</root>