Order entries by a category field alphabetically then paginate
In order to sort your entries by a related field you need to join the relations and the content table and sort your entries by the column you want. The it doesn't change the behavior of your paginate

{# the field ID of your relation field, you can as well grab it via #}
{# set field = craft.app.getFields().getFieldByHandle('carCategory').id #}
{% set fieldId = &gt;&gt; number &lt;&lt; %}
{% set entries = craft
    .entries
    .section('cars')
    .leftJoin('{{%relations}} as myrelations', '[[myrelations.sourceId]] = [[elements.id]] and [[myrelations.fieldId]] = ' ~ fieldId)
    .leftJoin('{{%content}} as mycontent', '[[myrelations.targetId]] = [[mycontent.elementId]]')
    .groupBy('elements.id')
    .orderBy({'mycontent.title': SORT_ASC})
    .all()
%}