One way to choose texture sizes is to have a target texel density relative to the size of an object. For instance, if you wanted 128 texels per meter, then an object 4 meters in size should have a 512x512 texture, an object 8 meters in size should have a 1024x1024 texture, etc. The same guideline can be applied to tiling textures as well.
Another thing to take into account is how close the camera can get to a particular object. If the camera can get very close, for example to a character, you would want a higher texel density. A character might only be 2 meters tall but you would probably want a lot more than 256x256 for her textures. Conversely, a mountain in the distance will never be seen up close, so it doesn't need a very high texel density.
is it better to always do high-resolution texture and then reduce it in the software (ie : increase the LODBias settings in UDK...)
I wouldn't use LOD bias settings to reduce textures. If you do that, you're still paying for the cost of the high-res texture in memory and loading time. Instead, reduce the texture in a preprocess, and only load the smaller version of it. It's still good to author the original textures at a high resolution so you have the extra detail in case you need it later.