In Starting Strength - which is basically very similar to StrongLifts - Rip tells you to eat, eat, eat. If you you hit a plateau, eat through it. I think you're going to find it very hard to build muscle with a significant calorie deficit because as you say the body needs extra calories in order to do this. I would say either keep the weight you lift the same for a few weeks/months until you get to your target BF before increasing calories, or increase calories and weight now and accept that the fat loss will slow down or stall.
FWIW I think the biggest mistake you can make if you are very active is to eat too little. You will just end up getting run down and tired all the time. This is from personal experience.