Welcome to FlyerTalk! Unfortunately, your requirements make this a tough ask. My recommendation for upgrading is to be as flexible as possible, both in terms of dates and in terms of connections. By limiting yourself to the shortest flights -- presumably one-stop itineraries through EWR -- and specifying particular dates, you're boxing yourself in quite a bit. The only thing in your favor is that April 18 is a Tuesday, which isn't a particularly popular day for business travel, which may make upgrading easier.

Even if you do get upgraded, that's going to be a very short and tiring trip.

If you like the price you see, you can go ahead and book now. The miles and upgrade co-pay are refundable if you don't clear, or if you end up changing your travel plans, and, as WineCountryUA noted, this isn't a bad time to book international trips for April. Keep in mind that you cannot upgrade the Basic Economy fare, so you'll need to purchase Economy or Premium Economy. Unfortunately, PE seems pretty pricy for your route on those dates. You may want to watch and see if the PE price comes down, even after you buy your Economy ticket.

Also, watch for a potential cash upgrade offer, as those can be a good deal.

Finally, just looking at the inventory on the EWR-BCN / BCN-EWR flights, your chance of an upgrade on Monday, April 24 seems particularly low. The inventory is J9 C9 D0... O9 A0 R0. UA isn't offering any discount business class or BE fares at the moment. That's generally a sign that they are at or above their traffic goals, and they believe they can sell the extra seats at a premium. That's also what's driving up the cost of the business class flight so much. If you could return on Tuesday 4/19 instead of Monday 4/18, the round-trip business class ticket would be $4400 each. Still not cheap, but a much better price than the $8600 you're seeing for a Monday return flight.

Also, if you're upgraded ahead of time, it's all or nothing -- either you both get upgraded or neither one of you do. That does mean that if UA opens one upgrade space, someone else can snag it if they're traveling alone.

If you're not upgraded ahead of time, your reservation will be split about 24 hours prior to departure, at which point you would clear independently, and it becomes possible that only one of you will get upgraded.

Hope this helps. Good luck!

As mentioned, PN won't do you any good. You need PZ. PN is only available to people in the highest, invitation-only tier of United MileagePlus.