Coinstar does not charge people 9% for changing USD -> USD, but they rather automate the process of converting large amounts of coins into a "format" that is spendable, as most banks will not accept large amounts of change/coin that is not "wrapped" by denomination.
The fact that a coinstar machine is expensive to produce as this kind of technology is not cheap (to count and sort coins deposited in mass) and needs to be audit-able will make it less likely that there will be a machine that converts change into bitcoin. Any operator would need to cover the costs of the machine plus some margin in converting their fiat into bitcoin
Interesting, every bank I have asked in the last several years accepts loose change, but not wrapped change (it has been 10+ years since a bank has accepted wrapped change from me). Most of them have their own coin counting machines and don't charge members to deposit the loose change. One of them even told me they don't have a coin counting machine, but will count my change by hand for no charge (and will not accept wrapped coins, and I was a member). We are only talking about 5+ banks here, but with 100% consistency, they accept loose change and not wrapped change, so either I live in the twilight zone, or Coinstar is for the unbanked and uninformed.