I was wondering if there is a synonym for the word group "increase by one".
Yes. There are several, although most of them like 'progress' (orig. "to go up by steps") have taken on expanded senses that obscure the exactness you're trying for. 'Increment' is the closest in current use, but "increasing by one unit on each iteration" is only going to be understood in programming contexts. Otherwise, people are going to take it as the distance between successive steps.
"If the shoe didn't fit, the shoe size was increased by one size."
Er, no, there's no single word that works there. Even if you used 'progress' or 'increment' there, it's just like 'increase' that you're going to have to specify the increments you're using.
The idiom for this situation is 'go up' or 'down':
"If the shoe doesn't fit, go (up|down) to the next size."
although, given the tentativeness of the proposed solution, it'd also be common to use some version of 'try':
"If the shoe doesn't fit, try the next size (up|down)."
I think it sounds weird because of the repetition of "size"[;] however, I think I cannot just delete the second "size".
You can't. Rephrase to delete the first one, as above.
Or does the sentence below sound natural to native speakers?
"If the shoe didn't fit, the shoe size was increased by one."
No, it doesn't, but not because the second 'size' disappeared. It's unnatural because you're using the past tense to propose tentative solutions—not to report the final answer—but talking about those tentative solutions as though they were final. A one-size adjustment might've still been too (small|large).
If the shoe didn't fit, we adjusted it up or down one size at a time.
with the implication "...until it fit". It's still odd that you're speaking in the past tense in a technical publication where you're presumably speaking generally or providing advice for future action, rather than reporting on your former forays into the fast-paced world of shoe sizing.
P.S.: The intended use is a technical publication, so please no colloquial terms and phrases.
Well, 'go (up|down)' is somewhat colloquial but it's not so informal as 'upsize', '+1ed', &c. It's basic and perfectly clear Germanic vocab that more of your readers will understand than latinate verbiage like 'increment', 'augment', or—Heaven forfend—'decrement' or 'wax greater employing an incremence of one'. As long as you're not trying to stay latinate just to sound smarter, it should be fine.