At some point before boarding international flights (either during check-in or at the gate), airlines check if you have the appropriate paperwork to enter the destination country, and in some cases for transit countries (passport and visa(s) or permit(s), if required). That's because if they bring a passenger to a country they don't have the paperwork for, the passenger will be refused entry and will be flown back (at the airline's expense) and the airline can be fined. So they'd rather stop them before they even board.
They use systems such as Timatic or Traveldoc to see what the requirements are, and have automated and/or manual systems to make these checks based on the itinerary and the documents presented. The exact rules may be a lot more complex than just "Ukrainians don't need a visa", and the interpretation of the results can be tricky.
Since France and Poland are both in the Schengen Area and passengers will enter the Schengen Area in France, they will check if you can enter France.
The relevant requirements for Ukrainian citizens travelling to France are:
Passport
Passport required.
Document Validity:
Passports and other documents accepted for entry must be valid for a minimum of 3 months beyond the period of intended stay.
Warning:
Passports and/or passport replacing documents issued more than 10 years prior to date of travel are not accepted
Visa
Visa required.
Visa Exemptions:
Nationals of Ukraine with a normal biometric passport (with an electronic chip symbol on the cover) for a maximum stay of 90 days. Information: The maximum stay is granted within 180 days.
(...)
Visitors must have proof of sufficient funds to cover their stay (at least EUR 120.- per day or EUR 65.- per day with a hotel reservation confirmation).
Visitors must have proof of accommodation. Exception: This does not apply to nationals of Austria, Belgium, Bulgaria, Croatia, Cyprus, Czechia, Denmark, Estonia, Finland, Germany, Greece, Hungary, Iceland, Ireland (Rep.), Italy, Latvia, Liechtenstein, Lithuania, Luxembourg, Malta, Monaco, Netherlands, Norway, Poland, Portugal, Romania, Slovakia, Slovenia, Spain, Sweden and Switzerland, and their family members.
Warning:
Visitors not holding return/onward tickets could be refused entry.
(...)
(it's basically the same thing for Poland, really)
So:
Do they have Ukrainian passports (and not Refugee Travel Documents issued by another country, for instance)?
Are the passports "normal" (ordinary) passports and not temporary/emergency passports?
Are the passports biometric? They should have this sign on the front cover:
Do the passports have at least 3 months validity left (actually 3 months beyond the intended departure date)?
Were the passports not issued more than 10 years ago?
Note that in most of those cases, I would expect the airline to say that there's an issue with the passport, not that they need a visa, but it may have been lost in translation somewhere.
Other possible issues (some are far-fetched, and most would not result in a "you need a visa" response):
- The names in the passport do not match the booking.
- The passport's chip was defective
- The passport was forged
- The passport was cancelled (declared as lost or stolen)
- They had one-way tickets or a return ticket beyond 90 days and the airline is going a bit too far
- There was a problem completely unrelated to passports or visas such as the payment for the tickets not having gone through, them being on a no-fly list or whatnot.
If their passports met all the conditions, and the reason given was really that they needed a visa, then the airline was evidently wrong. Depending on the airline, they may then be owed compensation for unjustified refused boarding.
IMHO the most likely case is that their passport was not biometric (which literally means they need a visa, but in practice means they need to get a new passport).
