First, show the sidebar, if it's hidden. From the menu bar, under View, select Show Sidebar.
If you load the shuffle manually (drag and drop songs on shuffle in iTunes)...
Find the shuffle in sidebar, under DEVICES, and select it. Click the toggle (little triangle to left of shuffle), to drop down the shuffle's content list, indented under the shuffle. Click Music there. Over to the right, the list of songs on the shuffle is shown. Select the song (or songs) you want to delete, and press the Delete key.
If you use automatic syncing to load the shuffle, please post back...