Modify ElementCriteria and use it for paginate
You can only modify a craft.entries criteria model with a field (→ Add custom element criteria attribute without a field type?). So what you have to do is to create a new custom field type with your plugin, and add such a field to the entry types you want to filter.

{% set entries = craft.entries.section('mySection').country('germany') %}


With that criteria model you would pass the value "germany" to your custom field type field "country". The field type would then use this parameter to modify criteria model's query.

Here's some code that should help you putting this together:

public function getInputHtml($name, $value)
{
    return;
}

public function modifyElementsQuery(DbCommand $query, $params)
{
    if ($params !== null)
    {
        craft()-&gt;businessLogic-&gt;addCountryCriteria($query, $params);
    }
}


You don't want the field to show up as an input field in the edit entry view, so we let getInputHtml() return null.

In our modifyElementsQuery method we just check if there's a parameter submitted (the country), before passing the criteria model's query to the service.

public function addCountryCriteria(DbCommand $query, $country)
{
    // Add conditons to the query 
    $query-&gt;andWhere($conditions, $params);
}


Your addCountryCriteria service can basically stay untouched, except that you can remove buildElementsQuery(), queryAll() and populateModels(). As you only want to modify the query.