Fastest query to filter product by countries
Since wrote you won't mind changing the design... Change the design.
Instead of that complicated logic with the flag and implicit inclusions/exclusions, just have a table that maps products to countries. Let's simply call it productcountry. If, and only if, a record for a country exists for a product in productcountry the product is available in that country.
The query then just uses some JOINs and a WHERE.
SELECT DISTINCT 
       p.*
       FROM product p
            INNER JOIN productcountry pc
                       ON pc.productid = p.productid
            INNER JOIN usercountry uc
                       ON uc.countrycode = pc.countrycode
       WHERE uc.userid = @userid;

For that you should try indexes on usercountry (userid, countrycode), productcountry (countrycode, productid) and product (id).
It will need a DISTINCT though because a product can be available in more than one country a user uses. (I silently assume here that the products are distinct by themselves, i.e. they have a key.) You can experiment, if you yield a better plan, if you instead use EXISTS and a correlated subquery.
SELECT p.*
       FROM product p
       WHERE EXISTS (SELECT *
                            FROM productcountry pc
                                 INNER JOIN usercountry uc
                                            ON uc.countrycode = pc.countrycode
                            WHERE uc.userid = @userid
                                  AND pc.productid = p.productid);

Here you can try indexes on usercountry (userid, countrycode) and productcountry (productid, countrycode).