You can use a static Map in your enum that maps Strings to enum constants. Use it in a 'getEnum' static method.  This skips the need to iterate through the enums each time you want to get one from its String value.
public enum RandomEnum {
    StartHere("Start Here"),
    StopHere("Stop Here");
    private final String strVal;
    private RandomEnum(String strVal) {
        this.strVal = strVal;
    }
    public static RandomEnum getEnum(String strVal) {
        if(!strValMap.containsKey(strVal)) {
            throw new IllegalArgumentException("Unknown String Value: " + strVal);
        }
        return strValMap.get(strVal);
    }
    private static final Map<String, RandomEnum> strValMap;
    static {
        final Map<String, RandomEnum> tmpMap = Maps.newHashMap();
        for(final RandomEnum en : RandomEnum.values()) {
            tmpMap.put(en.strVal, en);
        }
        strValMap = ImmutableMap.copyOf(tmpMap);
    }
    @Override
    public String toString() {
        return strVal;
    }
}
Just make sure the static initialization of the map occurs below the declaration of the enum constants.
BTW - that 'ImmutableMap' type is from the Google guava API, and I definitely recommend it in cases like this.
EDIT - Per the comments:
- This solution assumes that each assigned string value is unique and non-null. Given that the creator of the enum can control this, and that the string corresponds to the unique & non-null enum value, this seems like a safe restriction.
- I added the 'toSTring()' method as asked for in the question