Is it due to the bond formation creating energy that increases the entropy of the surroundings/universe?
There are multiple things going on with this question. First, we don't determine "feasibility" via entropy change of the system (entropy change of the universe, yes, but of the system, no). We determine feasibility via the free energy change of the system (which accounts for the net entropy change of the universe).
Second, you need to recognize that the rate of the reaction is dependent on the free energy difference between any stable intermediate and a subsequent transition state. So, making the enzyme-substrate complex less stable has zero impact on the rate provided it does not change this difference. In fact, it will speed up the reaction if the enzyme-substrate complex converts to the enzyme-product complex via a lower barrier pathway than the substrate to product does without enzyme.
Finally, you should note that enzymes generally don't bind very tightly to the substrate, for two reasons. The first is related to what we just said about barriers. If you decrease the energy of the enzyme-substrate complex relative to the substrate and free enzyme, you're actually slowing down the reaction and making it harder for the enzyme to work. Also, enzyme-substrate binding can be mildly correlated with enzyme-product binding (depending on product). If your product binds too tightly, it will inhibit enzyme turnover and also slow the reaction.