Show posts related to entry AND all posts not related to any entry
Building on this answer, and this question, here is what I would try:

Get the posts from the current city:

{% set currentCityPostIds = craft.entries.section('news').relatedTo(currentCityFilter).ids() %}


Get the posts with no city (uses search):

{% set noCityPostIds = craft.entries.section('news').search('-city:*').ids %}


Make one list of all the ids (twig merge filter):

{% set postIds = currentCityPostIds|merge(noCityPostIds) %}


Get all the posts with those ids:

{% set postsToPaginate = craft.entries.id(postIds) %}


Now you can paginate them:

{% paginate postsToPaginate.order("featured desc").limit(10) as pageInfo, pagePosts %}