Just brainstorming some ideas:
Have you looked up what cities your guests are arriving from directly before they go to your city? (E.g., Asunción, Curitiba, São Paulo, or some other cities)
I'd try to figure out what cities people are in when they decide to go to your city, and then put some advertising there: rack flyers, posters, partnerships with hostels in those cities, etc.
I don't know much about the hostels there. Are your competitors part of hostel networks that send them guests from other cities? I haven't been to Brazil, but there were two large networks in Argentina when I was there (HI and Minihostels). I wonder if that could be a factor.