No puedes borrar fotos en Galaxy S4 porque están sincronizadas de Facebook/Google+: desactiva la sincronización

Las fotos que muestran un icono de Chrome / Picasa / Google+ / Facebook y no tienen botón «Eliminar» están en la nube, no en el teléfono.

Para poder borrarlas localmente:

1. Ve a Ajustes > Cuentas > Google > [tu cuenta] > Sincronización > desmarca Fotos de Google+ / Picasa.
2. O Ajustes > Cuentas > Facebook > desmarca Sincronizar contactos/galería.
3. Vuelve a Galería; ahora esas fotos tendrán botón Eliminar (borrarás la copia local; la original queda en la nube).

Vídeo guía: Samsung Galaxy S4 - Cómo borrar fotos de galería sincronizadas.