despegar.com is a flight search engine for Latin America that seems pretty good. (I found out about it recently when someone here on Travel SE mentioned it.)
You should be able to buy the tickets directly through despegar, but I have no experience of how well that works. Alternatively, just use it to find airlines / schedules / prices, and then book via the airline.
(The site is apparently only available in Spanish and Portuguese though.)
I had a quick look at flight options between Colombia & Paraguay, and they seem quite poor: apparently there aren't any direct flights, and it isn't cheap. Prices of return tickets (incl all taxes and fares):
- Bogotá-Asunción from USD 774. Travel time from 8h 30m (via Lima).
- Medellín-Asunción from USD 764 Travel time from 8h 10m (via Lima).
I got similar results (quite expensive & slow, with no direct flights) from other search engines like eDreams. So it seems Colombia-Paraguay just isn't the most convenient route to fly.
I was wondering why, and well, turns out that Asunción's Silvio Pettirossi International Airport (ASU)—Paraguay's main international gateway—isn't exactly a major hub. You can only fly to eight international destinations from there (Buenos Aires, Miami, Panama City, São Paulo, Lima, Rio de Janeiro, Santa Cruz de la Sierra and Santiago de Chile).