Förstemann (1900) discards a connection between OS Badu, OHG Batu and a name element BAUD, but you have a point here. The French shift of al to au occurred probably too late to explain the Baud- in Baudovinia/Baudonivia. Förstemann suggests a derivation from Ancient
German beudan, Gothic biudan, "to command". This name element occurs later in names like Bodo.