About the pagination example you mentioned: Rather than use link relations, pagination might be better done with URI Templates. This is a spec [1] that allows passing a URI with placeholders to the client which can then fill them in without every option being described up front by the server. It's still a new-ish area but there are library implementations for most major languages now.
Explicit link relations aren't the only way to do hypermedia and the best practices are still moving/being discovered.