Average shoe size should fit OK
The crank specs that matter are the length from the axle centre to the pedal centre, 170mm is the standard size, but sometimes up to 175mm.
Either should fit.
It may be that the angle of the head-tube is too steep (ie the frame is bad). More probable that the fork is wrong. Rake is the offset from the steering axis generated by bending the fork blades. Usually the wheel is placed a few cm forward of the steering axis, the exact amount varying. Too little rake and you may get interference.
Something is wrong and needs to be put right, so dont accept the bike shops excuse.