La primera entrada de paraguaya con tal definición aparece en 1936. Nótese que especifica que se usa esta palabra en América1:
Paraguaya. f. Amér. Fruta de hueso semejante al pérsico y de sabor también parecido, de forma aplastada y de mucho consumo en Europa.
- Diccionario de la lengua española (1936)
Paraguayo lleva otra significación más antigua2 en Bolivia:
paraguayo.
I. 1. m. Bo:E. Rosquete hecho de azúcar, almidón y clavo de olor.
En inglés los paraguayos (la fruta) son también conocidos como "doughnut peach".
Dado todo esto, me parece probable que tome su nombre de los rosquetes por su forma similar ("doughnut-shaped"), como ha pasado en inglés.
Notas:
1. De hecho, esta fruta solía llamarse por otro nombre en España:
— melocotón tomatero o paraguayo: es «chato y chafado», la piel rojiza
y la carne blanca. Con este nombre se designa la variedad de carne
blanca llamada paraguayo; esta denominación es de reciente introducción,
pues para los mayores el único nombre conocido es el de melocotón
tomatero.
• Denominaciones populares de las especies frutales en Alfaro (La Rioja) (1997)
2. La primera entrada de paraguayo con la definición de una especie de rosquete antecede a la de la fruta por dos décadas:
PARAGUAYO, YA ... || Amér. En Bolivia, rosquete de azúcar y almidón.
• Diccionario de la lengua española, Alemany y Bolufer (1917)
3. No eres la primera en preguntarse esto:
Se llama, "La Paraguaya". La denominación nos sorprendió y, lógico, inmediatamente indagamos su genealogía, su procedencia. "La Paraguaya" es una especie de melocotón, de la familia del durazno. Petiza. Jugosa. Riquísima. Pero, de dónde venía su nombre? Era un misterio que nos intrigó y nos lanzó en pos de su revelación. Nadie, entre nuestras amistades, escapó de la indagación, del interrogatorio. Todos sin embargo estuvieron contestes en acusar la más sorprendente ignorancia. Por ello, el enigma se mantuvo.
Como tantas cosas populares, "La Paraguaya" tiene también el origen de su apelativo perdido en la noche inmemorial. Puede haber llegado a España acompañando el regreso de los viejos señores de la aventura o con algún indiano reintegrado al solar patricio. O tal vez, nació en la trama desconocida y romancesca de...
• Por los caminos del viejo mundo: visión de un periodista paraguayo, Sindulfo Martínez (1964)