It's late to be seeking award flights to Europe, especially for two people who wish to fly (presumably together) first or business class to a popular destination like Paris. But here are a few things to keep in mind.

1) Both UA and AA offer one-way awards for half the miles of a roundtrip, while DL and US charge the same amount in miles for one-way and roundtrip miles. (DL is changing its policy in 2015, but that's too late to help you now.) Looking to use AA miles in one direction and UA in the other may increase your options.

2) Until March 30, US miles can be redeemed for travel on US, AA and UA and other members of Star Alliance, such as LH, LX and OS. Beginning March 31, those miles cannot be used to book travel on UA or other Star Alliance members (with some exceptions), but can be used on AA's partners in Oneworld, such as BA, AB and IB. BA has prohibitive surcharges on award travel, but AA and its other partners are more reasonable. (IB award flights cannot be booked online, but require a phone call.) The fact that US is about to switch alliances may afford you more choices, at least for the next couple of weeks.

3) If you can't find award flights to Paris, you might consider flying to nearby airports such as AMS, BRU or even DUS.

4) If need be, taking separate flights and/or flying economy (at least one-way) might increase your likelihood of finding award seats.