El problema se te presenta porque tienes un campo llamado cp y de igual forma has creado una variable local en MySQL que posee el mismo nombre. Esto en MySql es un error ya que el gestor termina interpretando la referencia al campo de la tabla como la variable recien creada.
Where cp=cp
Lo estás interpretando como el campo cp de la tabla empleado sea igual a cp que es la variable definida localmente para el stored procedure.
Ahora MySql lo "entiende" como la variable local definida cp sea igual a la variable definida cp
Solucionas tu problema cambiando el nombre de tu variable local por otro. Por ejemplo:
delimiter //
create procedure elimdato(in id_emple int(6),nocp varchar(5))
begin
DELETE FROM empleado WHERE cp=nocp;
end //
call elimdato(1,40855);
Espero sea de ayuda. Un Saludo!