Foreigners residing in Japan are eligible to participate in furusato nouzei, but Americans might want to note the following clause in the section "Tax Must Be the Legal and Actual Foreign Tax Liability" in Publication 514 Foreign Tax Credit for Individuals[1], which states:
>Subsidy received. Tax payments a foreign country returns to you in the form of a subsidy do not qualify for the foreign tax credit.
>The term “subsidy” includes any type of benefit. Some ways of providing a subsidy are refunds, credits, deductions, payments, or discharges of obligations.
Whether or not furusato nouzei falls under this clause seems to be up for some debate, and AFAIK the IRS hasn't made a public determination on it either way. I don't risk it, but I am under the impression there are some that do.
Alternatively, the furusato nouzei portion could be not included in the tax credit? But would it be worthwhile...? Sounds like it depends on the situation and frankly seems like a lot of work to get a few gift baskets.
[1]: https://www.irs.gov/publications/p514#idm139978451112272