Thankfully, Microsoft did a good job of re-assigning the shortcuts to semi-familiar positions. Although you won't see it in the menu, you can use control-H to bring up the replace dialog, and control-K to cut rows or columns. I haven't tested it extensively, but I imagine other "replaced" command-key shortcuts can also be reached with the control key.
If you don't like these keys, of course, you can reassign them yourself using the keyboard editor in the Office apps (eg Tools -> Customize -> Commands tab -> Keyboard... button in Excel).

