Sorting Entries field results by category
It’s not totally clear from your question where you’re building the relation to the categories,
but I have a feeling that this is the solution you’re looking for.

{% set groupParam = '{ object.categoriesFieldHandle.first() ? object.categoriesFieldHandle.first().title : "No categories" }' %}
{% for groupTitle, entriesInGroup in entry.entriesFieldHandle|group(groupParam) %}
    {{ groupTitle }}

    {% for entry in entriesInGroup %}
        {{ entry.title }}
    {% endfor %}
{% endfor %}