No es necesario agregar esa dependencia, esta declarada en el bundle, de todas formas según packagist como lo tiene el OP es correcto, pregunta tonta, tienes minimum-stability declarada a dev ?
En cualquier caso puedes darle una ojeada a
https://github.com/KnpLabs/KnpPaginatorBundle, es el mas utilizado(y actualizado...).