When my dog was new to my house it took me sixth months to figure out gut issues. He too had a parasite, which complicated things. The parasite will clear with treatment. Give that time and expect messy poops in the process. It's going to be hard when you are dealing with multiple variables. Just get to the stage where a stool sample shows no active infection.
Try homemade chicken, rice, and pumpkin for a few meals to see if that firms up stool. It should be gentle and provide fiber as a bulking agent. Do not use this as a permanent food as it lacks a complete nutrient profile.
Then start trying unique proteins. Some animals have an IBD-like illness that can be triggered by certain animal proteins. Chicken and fowl is a common issue. Beef can be problematic too. You might try things like lamb, rabbit or kangaroo-based foods. There are also hydrolyzed protein foods available by prescription for animals who are suspected to be allergic to standard feeds. A veterinary allergist can confirm allergies as well, though you'd usually notice other symptoms, like a dull coat, scratching, red belly, or chewing of feet.