Žádný zázračný program na zvětšování neexistuje. Pokud je původní foto (předhloha) malé, tak zvětšenina bude vždy rozmazaná a kostičkovaná.
Podívej se třeba na tuto tabulku:
http://www.fotostar.cz/objednat-foto/skutecna-veli kost-foto.html
Čili pro tisk na formát A4 by měla mít fotka rozměr minimálně 1344 x 1792 bodů.

Jaké má ta tvoje fotka rozměry/rozlišení?

Jinak pro práci s fotkama používej třeba IrfanView nebo XnView, na Malování zapoměň...