If your other shuffle still works fine, and you can't sync to this one either manually or automatically, AND you already did a Restore on it, it may have a hardware problem, possibly with its flash storage. Part of its storage is fine, so you can do a Restore and start a sync, but it fails along the way and becomes corrupted.
One more thing you can try is to reformat the shuffle's storage outside of iTunes, using Windows, like it's a USB flash drive. On shuffle's Summary settings screen, Enable disk use (if it's not already) so that it appears in Windows with iTunes not running. Use Windows to reformat the iPod. Use FAT32 (not ExFAT or NTFS) as the disk format. If there's an option to do a quick format, do the full format.
If it reformats successfully, run iTunes. You must do a Restore in iTunes to install shuffle's onboard software (it is currently completely blank), whether you're prompted or not. After the Restore, try syncing some songs again, using either method.