This is in no means an elegant solution, and can almost certainly be improved. But it did its job just fine.
{% set veterinarians = craft.entries({
section: 'veterinarians',
order: 'premiumVet desc, postDate desc',
}) %}
{# more filter/search params #}
{% set entriesPerPage = 20 %}
{% set page = craft.request.getParam('page') %}
{% set page = page ?: 1 %}
{% set offsetParam = (page - 1) * entriesPerPage %}
{% set veterinarians = veterinarians.offset(offsetParam).limit(entriesPerPage) %}
{% set isNextPage = veterinarians.offset(page * entriesPerPage).limit(1)|length %}
{% set queryString = craft.request.getQueryStringWithoutPath()|replace('/page=\\d+&?/') %}
{% set queryString = queryString ? '&' ~ queryString %}
{% set nextUrl = isNextPage ? craft.request.url ~ '?page=' ~ (page + 1) ~ queryString %}
{% for entry in veterinarians %}
{# loop entries #}
{% endfor %}
{% if nextUrl %}
<div class="js-pagination-trigger">
<a href="{{ nextUrl }}">Weitere anzeigen</a>
</div>
{% endif %}