Yes, this will be the most difficult challenge to solve. You could make the lottery-reward decrease exponentially with the number of transactions in the block, making it unprofitable for miners to add extra fake transactions. Since they will have the chance to loose all the high fees for a slim chance on a small reward. In other words: each extra fake transaction will mean they pay more to win less.
The miner could add just a single high fee transaction and be guaranteed the lottery. In game theory this would be the optimal choice unless the fees were worth more than that. So it puts a minimum economical fee on tx at higher than what a miner can simply game for himself. The higher the fee the lower the utility of the network.
Another solution could be that the network rejects blocks of which a certain percentage of the transactions is not in their memory pool. That means the miner has to broadcast those TX's first, and if another miner mines the block, the miner who created the fake TX's looses a lot of money.
This is a non-starter. It is an unsolved problem on a non-deterministic system. It is fairly easy for attackers to game in order to orphan blocks of legit miners. Still lets assume you succeed and the system can't be gamed in any way. New coins subsidies users not miners and miners receive only tx fees of legit transactions. The network remains far less secure or tx fees need to be excessively high. Neither of which would make the network attractive relative to Bitcoin. What problem are you trying to solve other than "I don't mine so I don't like it that other people get subsidized coins"? The primary purpose of mining is to secure the network. Any system that discourages mining is working against the basic interests of the network. A network that is more secured is worth more than one which has inferior security.
The new coins are a subsidy. The purpose of a subsidy is to encourage a specific activity. In the case of Bitcoin that activity is securing the network.