By definition testing EVERYTHING will take INFINITE TIME. Which I bet is less than optimal (unless your boss is OK with that - then you just found safe job for life :-)
So you need to agree with your boss about some metrics to limit and prioritize "everything".
Make a survey among your customers which OTHER applications they use, on which platforms. Or make educated guesstimate according to literature, your specific industry etc.
Then, sort by platform and usage. Spend available resources on most widely used platforms/apps. As more testing resources are available (or you are able to automate part of tests), you can test more obscure platforms/apps. Rinse, repeat.
Plan where your application is expected to be 2 years from now (marketing department has idea), and what usage patterns will be expected then.
Some suggestions: XP is dead, I cannot imagine wasting ANY resources on that. Tests/scenarios developed now should be valuable in the future too. If you have limited capacity now, it does not make sense to spent it on platform with limited future. And so on.
If you cannot agree on priorities with your boss, as "where to start". Only one can be first. And go from there.
If one of your requirement is test automation, and you cannot run automated test on one platform: Good news! You just eliminated one dimension of your problem space! (If the platform is obscure enough to be ignored).
Develop some simple sanity tests for more obscure platforms/app combination, and more detailed/specific/automated for more important ones. There is no rule saying that you need to pay equal attention to important platforms and obscure ones, just the opposite. As any engineering task, it is about finding good compromises (less attention to less important stuff).