Currently miners are compensated for this work with a subsidy. The subsidy declines over time and will be replaced by tx fees.
Once all blocks are found - what happens to offline wallets (paper wallets)? E.g. today one can use to private key to fund his account (e.g. MtGox). But there are no tx fees in this process.
Nothing happens to offline wallets. Or online wallets, for that matter. You seem to be seriously misunderstanding something. What do you suppose MtGox (or anyone)
does with those private keys? They use the private keys to sign transactions to spend the coins! Private keys have no other function than to sign transactions, and paper wallets (actually, all wallets) have literally no value except for the transactions they allow the bearer to sign. And of course, these transactions will have fees.
So will the funds in offline/paper wallets then be lost (because: inaccessible).
There is no way to "access" funds other than signing transactions to spend them, which can be done as long as the private key exists in some form (offline or otherwise). The only way for funds to become inaccessible is for the private key to be lost.