As everyone already has said, there is no wallet provider that pays interest on your stored bitcoin.
For someone to pay interest, the bitcoin needs to be invested somewhere (lending or trading) and hopefully returning higher interest than what they pay out. This is how normal bank savings accounts work. The beauty of bitcoin is that you can do this yourself and there are heaps of options, but you need to understand the risk involved. So do your own research.
Following are a few options:
Magnr provide a savings account which pays 2.35% (low risk)
BTCPop have a 5% savings account which is low risk and then a range of pooled investments which can pay up to 50% but are higher risk as the funds are used for peer-to-peer lending.
Bitfinex have a margin-funding system where you can lend your bitcoin for others to trade. Returns vary and it sounds crazy but is fairly well run.
Then there are the ponzis/HYIPs - high interest but extreme risk - you have been warned.
The basic rule is: the higher the interest paid, the higher the risk.
Check out
www.stacksofcoin.com/invest-bitcoin for more info.