(Paper) Dart and (Paper) Arrow
These terms were used from at least the 1860s. However, not all of these designs were what we would today recognize and call 'paper planes'. Some clearly looked like the darts thrown at dart boards.
There are 19th century references (with images resembling paper planes) to
'paper dart' and 'arrow' (UK & US sources)
'ein Wurfpfeil' (a dart) (German source)
'flèche de papier' (paper arrow) (French source)
David Mitchell, a paperfolding designer, seems to have researched this in some detail on his webpage The Paper Dart / The Arrow.
The image below, from a book published in 1864 but with foreword dated May 1863, is from Hermann Wagner's 'Spielbuch fur Knaben'. In German, it was called simply "Ein Warfpfeil" [sic] (a dart).
The earliest instructions Mitchell found for making what we now know as a paper plane were in the 1864 edition of Every Little Boy's Book under the heading 'PAPER DART' and with a very small picture.
In French, it was called "La flèche de papier" (the paper arrow). The image below appeared in 1880 in T de Moulidars' 'Un million de jeux et de plaisirs'.
'Arrow' was also used in the New York publication 'The Kindergarten Guide' from circa. 1882 with the following diagram:
It's important to note that not every 19th century reference to a 'paper dart' or 'arrow' refers to something resembling a paper plane. This is clear from the evidence presented on Paper Darts and Flights where there are several illustrations which are clearly darts (sometimes including a pin in the tip), not planes. See, for example, this one:
Image taken from The Popular Recreator, 1873
Also, the circa. 1786 reference to a paper dart (cited in this reddit post) by the English actor Charles Mathews is inconclusive as to exactly what the then circa. 10-year-old actor-to-be was actually throwing:
This was about the year 1786. Bishop, the head master, wore a huge
powdered wig, larger than any other bishop's wig. It invited
invasion, and we shot paper darts with such singular dexterity into
the protruding bush behind, that it looked like "a fretful
Source: Mrs. Mathews, 'The Life and Correspondence of Charles Mathews' (1860)
Interestingly, on China, David Mitchell states:
It is commonly stated that paper planes originated in China over 2000
years ago as a development of paper kites. I can find no evidence
whatsoever to back up this assertion. It probably arises due to a
confusion between paper planes and paper kites.
All images taken from various pages on David Mitchell's 'Origami Heaven' website.