relate pagination to entry on page
You would need to pass the current pagination page number with your entry links and than make Craft
respond to URLs in a format like this: example.com/my-section/p2/my-entry-slug.

I guess this is more complicated than you'd think, as this is probably not possible to do with
the default paginate tag and its preset routes. And I also don't know of a way to combine the paginate
tag's page token with custom routes.

So I believe there's no other choice left than replacing paginate with a custom solution replicating its
functionality.

This is possible with dynamic routes and some logic in your templates. So you'd first have to set up a route
with a [page] and a [slug] token, which you can then access in your template.

my-section/p[page]/[slug] and
my-section/p[page]

I'll give some example code (untested and incomplete), to help you get started with the template.

All the pagination links build upon the route's page variable used in craft.entries's offset and limit parameters. With custom routes you also have to query for your entry entry model manually, I set it up to get the page's first entry
if there's no slug variable set from your route.

{# Set params #}
{% set params = {section: 'orchard'} %}
{% set entriesPerPage = 5 %}

{% if page is defined %}
    {% set offsetParam = (page - 1) * entriesPerPage %}
    {% set pageSegment = '/p' ~ page %}
{% else %}
    {% set offsetParam = 0 %}
    {% set pageSegment = '' %}
{% endif %}

{# Get the entry model #}
{% if slug is defined %}
    {% set entry = craft.entries.slug(slug).first() %}
{% else %}
    {% set entry = craft.entries(params).offset(offsetParam).first() %}
{% endif %}

{# Get pagination params #}
{% if page is defined %}
    {% set entriesOnNextPage = craft.entries(params).offset(offsetParam + 1) %}

    {% if entriesOnNextPage|length %}
        {% set nextPageSegment = '/p' ~ page + 1 %}
    {% endif %}

    {% if page == 1 %}
        {% set prevPageSegment = '' %}
    {% else %}
        {% set prevPageSegment = '/p' ~ page - 1 %}
    {% endif %}
{% else %}
    {% set entriesOnNextPage = craft.entries(params).offset(entriesPerPage) %}

    {% if entriesOnNextPage|length %}
        {% set nextPageSegment = '/p2' %}
    {% endif %}
{% endif %}

&lt;article&gt;
    &lt;h2&gt;{{ entry.title }}&lt;/h2&gt;
&lt;/article&gt;

&lt;nav&gt;
    {% set entriesOnPage = craft.entries(params).offset(offsetParam).limit(entriesPerPage) %}

    {% for entry in entriesOnPage %}
        {% set image = entry.mediaThumb.first() %}

        &lt;a href="/my-section{{ pageSegment }}/{{ entry.slug }}"&gt;
            &lt;img src="{{ image.url }}"&gt;
        &lt;/a&gt;
    {% endfor %}

    {% if prevPageSegment is defined %}
        &lt;a href="/my-section{{ prevPageSegment }}"&gt;Previous Page&lt;/a&gt;
    {% endif %}

    {% if nextPageSegment is defined %}
        &lt;a href="/my-section{{ nextPageSegment }}"&gt;Next Page&lt;/a&gt;
    {% endif %}
&lt;/nav&gt;