Limit balancing results by a column
Something like this, then?

SELECT  fk_location, 
        search_token,
        priority,
        ROW_NUMBER() OVER ( 
            PARTITION BY fk_location 
            ORDER BY priority, last_started_execution )
          AS Ranking
FROM    search_token
ORDER BY Ranking, fk_location 
LIMIT 20000;