You are running against a list of unknown size (vehicles), so even a single check is quick, you can not predict the final time (it is actually O(color) + O(n-color))...
As you are not interested in any car has different color from the one you passed in, you may do a pre-select of only the cars with the same color... Something like this:
var CheckList = vehicles.select(car => car.Color == veh.Color);
foreach (Car x in CheckList)
{
}
Your inner computation is also unclear...
coun
seams to be unused and unnecessary...
You also can cut the check if even all the letters left are mach you will not reach the 4 boundary... (something like (db + (6 - i)) < 4)