I have iCloud Safari bookmark syncing set up on two Macs and an iPhone. Is it possible to delete a bookmark (or set of bookmarks) from one machine only, so that they continue to exist on the other two devices?
As any changes performed to an iCloud-Sync service will be pushed to all other iCloud-Sync devices, your only option would be to unsync the desired device form iCloud's Safari and then delete the bookmarks.
Bear in mind that once you re-enable the Safari's Sync, all of its data will be merged together.
Cleaning iCloud Bookmarks Procedure:
Turn off bookmark syncing on all devices and on computer.
Clean /file /sort Safari bookmarks. Quit Safari.
Locate bookmarks.plist Safari folder in ~/Library. Drag to the desktop.
Start Safari. Bookmarks should be blank.
Turn Safari bookmarks sync back on. Let it sync to iCloud.
Quit Safari, move the ,plist back ~/Library/Safari.
Start Safari. Edited bookmark .plist is back in place. Let it sync to iCloud.