I agree with abbajbryant, your service shouldn't know anything about the http layer, or any layer above it (the object owner).

You are almost there though with your current implementation. Using a listener or the Delegation Pattern is nice way to handle this but it needs to be implemented in a way that is flexible with any object that instantiates it. Therefor we can't rely on $listener->actionFails() returning an object that has a method called withErrors (unless specifically docblocked because this is not a static language). You could have Listener->actionFails expect an $errors parameter which then does what it wants with those errors e.g. pass it to a redirectResponse.

E.g. Controller

<?php
    public function postSignin (){
        //...
        return $this->authenticator->attempt($input , $remember, $this);
    }

    public function actionFails(MessageBag $errors)
    {
        return $this->redirector->route('route.name')-withError($errors);
    }

Service

<?php
class Authenticator {
    //....
    public function attempt( $credentials , $remember, ListenerInterface $listener )
    {
        if ( ! $this->signin_validation->isValid( $credentials )){
            $messages = $this->signinValidation->getMessages();
            return $listener->actionFails($messages);
        }
        //...
    }

}

One last thing is your listening interface is very generic. Perhaps you need an AuthenticationListenerInterface instead. Instead of implementing the generic actionFails method it could implement authenticationFails. This way each of your services can gain more control over what each listener can listen for and what parameters are passed to those listener methods.

So to answer your questions

Should redirects be in the service or the controller ? Controller

Should I have a different ListenerInterface for each service ? I would, but it depends on the needs of the system.

Is there any other misunderstanding of the pattern in the code ? Your pretty close. It just needs some refining.