A completely elementary proof can be found on page 561 of the Nov 2012 edition of The Mathematical Gazette, where a descent mechanism first used by Stan Dolan in the March 2012 edition is adapted (as per his challenge to the “interested reader”) to solve both of Fermat’s “elliptic curve” theorems. The method uses math which was clearly available in Fermat’s time, and in particular to Fermat himself.
I personally believe this finally puts to rest any questions of whether Fermat could have had a proof of these two claims.