I am trying to wrap an external type using my own type, as outlined in the linked rust playground.

The external type stores a closure on initialization:

struct ExternalType<P> {
    predicate: P,
}

impl<P> ExternalType<P>
where
    P: FnMut(u8) -> bool,
{
    fn new(predicate: P) -> Self {
        ExternalType { predicate }
    }
}

My "newtype" uses this ExternalType (without exposing it), but uses a different closure, e.g., a different argument type, which is converted internally:

struct MyType<P> {
    ext: ExternalType<P>,
}

impl<P> MyType<P>
where
    P: FnMut(u8) -> bool,
{
    fn new<Q>(user_predicate: Q) -> Self
    where
        Q: FnMut(u32) -> bool,
    {
        // This fails to compile since the closure is not of type `P`.
        let f: P = move |num| user_predicate(num as u32);
        Self {
            ext: ExternalType::new(f),
        }
    }
}

Without changing the signature of my user_predicate (the actual code is a bit more intricate), is there any way of storing this closure?

I know that every closure has its own type and therefore the implemented closure does not match the given type Q, but on the other hand I have no idea on how to implement or annotate this fact in my type and especially not in the impl block.

I've seen the question regarding on how to store a closure in a struct but it doesn't really answer my question.

You can do this by instead of returning Self, return an impl type (playground)

fn new<Q>(mut user_predicate: Q) -> MyType<impl FnMut(u8) -> bool>
where
    Q: FnMut(u32) -> bool,
{
    let f = move |num| user_predicate(num as u32);
    MyType {
        ext: ExternalType::new(f),
    }
}

Future rust

This will be more ergonomic later with type alias impl trait. This will let you give the closure a name:

type P<Q> = impl FnMut(u8) -> bool;

which you can then use as MyType's generic:

impl<Q> MyType<P<Q>>

(playground)