Paginate entries when I do not have a criteria model?
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+&amp;?/') %}
{% set queryString = queryString ? '&amp;' ~ queryString %}
{% set nextUrl = isNextPage ? craft.request.url ~ '?page=' ~ (page + 1) ~ queryString %}

{% for entry in veterinarians %}
    {# loop entries #}
{% endfor %}

{% if nextUrl %}
    &lt;div class="js-pagination-trigger"&gt;
        &lt;a href="{{ nextUrl }}"&gt;Weitere anzeigen&lt;/a&gt;
    &lt;/div&gt;
{% endif %}