Gallium is found everywhere, it doesn't make sense to actively search for it because it doesn't concentrate anywhere. That's the whole problem. There is little that distinguishes bauxite ore from my backyard in terms of the amount of gallium that can be extracted.

The advantage of extracting it from certain ore waste streams is two-fold even though they don't contain much gallium. First, the chemical processing cost varies with the chemistry of the rocks you extract the gallium from, and certain types of ore waste such as bauxite, zinc, etc are cheaper to deal with. Second, these rocks have already been dug out of the ground as part of a mining operation, which is much cheaper than strip mining an arbitrary place to extract the same trace quantities of gallium -- you get to free-ride on the extraction costs of the primary mineral someone already paid for. If it doesn't matter where you dig, then all you can really optimize for is the processing cost of where someone already dug.

It would make no sense to increase bauxite production for the purpose of gallium production. Extracting gallium from bauxite is only economical to the extent that there is healthy demand for the aluminum produced from that bauxite. This is common in mining operations -- a secondary mineral that cannot be economically mined by itself becomes profitably extractable from the same ore if and only if the primary mineral is sufficiently profitable. Many less common metals are produced solely via secondary extraction because they cannot be profitably mined directly even when they concentrate.

wouldn't it also increase tailings thus we would just change our pollution problem from co2 to toxic mining waste? I mean aren't tailings from bauxite highly toxic?

No, bauxite processing is pretty benign. Strong hydroxides are used to extract the aluminum. Conveniently, a fraction of the gallium in the ore also leaches into the same hydroxide solution, so you can extract it by processing the waste solution after the aluminum has been precipitated. Any ore that uses strong alkali extraction is a candidate for cheap gallium extraction.

Bauxite processing produces iron, silicate, and similar minerals. Nothing anyone would identify as toxic. The alkali hydroxide solutions are recycled because they are one of the most expensive inputs. Nothing to worry about as such things go.

Right, but it's fair to say the real pollution from bauxite comes from the production of aluminum. It's often said that aluminum is solid electricity and if the electricity used to produce it comes from coal then its production is polluting, if from clean energy then it isn't (well, at least it's minimal).

The tailings from the Bayer process for extracting aluminium oxide from bauxite aren't toxic. The remains ("red mud") have an elevated pH from the residual sodium hydroxide used in the extraction of the ore but that's about it. There's a lot of it though and that sheer amount makes it a bit of an environmental problem as Red Mud has limited industrial use and much of it will be dumped / stored somewhere.