In the U.S. at least, a lot of these CoinStar machines are now owned and operated by the store or other venue in which they're placed, as a convenience to customers, and the fee for using it is waived.
These machines, even without a fee attached, are still beneficial to the store, for two reasons. First, they bring in potential customers; the machine usually spits out a ticket that you take to the cashier, meaning you pass by all the impulse items they put in the checkout lines, and someone using the change catcher will invariably pick up a pack of gum or a magazine to spend your newfound wealth. The fact that one store has a change machine while another doesn't can also be the difference between choosing that store over the other for a planned shopping trip.
Second, and less obvious, a store that owns a CoinStar machine has full access to the change people put in it (hey, they own the machine and are paying out cash on the receipts it spits out). During normal use of a cash drawer or register to take in money, large bills ($20/20€ or larger) are accumulated to be "broken", small to medium bills (1-10 units) stay roughly static in number as payments are made and larger bills are broken, and coins are invariably depleted as change is paid out. This means the average retail store needs a constant incoming supply of coinage, and that generally happens either through armored car service or similar commercial banking (which costs the store money), or through "change catchers" like gumball machines (which usually can't supply all the needed denominations). The Coinstar machine effectively reverses at least a portion of this attrition of coins and accumulation of large bills; the store can now receive coins and pay out large bills as a part of its day to day business, reducing or even eliminating the need to have a bank or armored car perform this service.
Anyway, check and see whether the CoinStar machine you last used is still operating on a percentage-fee basis; it might be the case that the store has purchased the machine outright and is offering its services free of charge. If not, look around; other stores may be waiving the CoinStar fee where this one isn't (or they may have similar, non-CoinStar branded machines). Lastly, as other answers have mentioned, if you cash out in the form of a gift card, there's no fee, so you can pick a gift card to a store you're likely to visit anyway; in the U.S. there are a lot of good choices, like home improvement stores, Starbucks, major department stores/clothing retailers, and even an airline.