I agree 4k records isn't anything to worry about. I suggest querying the phone numbers and the primary id of the table, stripping all characters from phone number and then manipulating it to be the format you want. Or, you could keep it as only numbers and use your front-end to modify the number every time you display it. Below is a little untested script you can try to use. Doesn't handle extensions and expects there are 10 numbers.
// mysql_connect stuff
$q = mysql_query("Select phone_id, phone_number From phones");
while($r = mysql_fetch_assoc($q)) {
$num = ereg_replace("[^0-9]", "", $r['phone_number']);
if(strlen($num) == 10) {
$num = substr($num, 0, 3) . '-' . substr($num, 3, 3) . '-' . $substr($num,-4);
}
$update = mysql_query("Update phones Set phone_number = '" . $num . "' Where phone_id = " . $r['phone_id']);
// updated?
}