Have you tried using merge coins functionality? It could potentially merge your coins without causing any conflicts with gas requirements. This feature was added to reduce the hassle of manual coin management. The process is designed to represent what you want in the transaction while deferring the source of the coins until you build and sign the transaction.

You don't need to manage coins manually. You can simply use coinWithBalance, and the SDK will handle finding and merging the coins for you automatically. Try specifying the coin you want to use for paying the fees separately, as this might resolve the issue with the gas. Here's the SDK documentation link for more information: Gas Payment.