Display only entries relevant to users' country
One nice way to handle things like this is to collect the ids for all the entries you want, use those ids for the ElementCriteriaModel you need for the pagination, and then paginate.

Collect the ids (use merge to create an array of the ids):

{% set ids = [] %}

{% for entry in craft.entries.section('news') %}
  {# loop through regions  #}  
  {% for region in entry.regions %}
    {# loop region's countries  #}
    {% for targetCountry in region.countries %}
      {% if targetCountry == currentUser.country %} 
        {% set ids = ids | merge([entry.id]) %}  
      {% endif %}
    {% endfor %}
  {% endfor %}
{% endfor %}


Get the entries for pagination:

{% set unpaginated = craft.entries({
  id: ids,
  limit: 10
}) %}


Finally, the pagination:

{% paginate unpaginated as pageInfo, pageEntries %}
...