The following link is from the Oracle Service Cloud developer documentation. It has an example of setting a contact custom field using Java and Axis2, which would likely give you most of the information that you need in order to set your custom field.
At a high level, you must create an Incident object and specific the ID of the incident that you want to update. Then, you must create the custom field object structure using generic objects (because each site can have its own unique custom fields). Ultimately, your SOAP envelope will contain the node structure that you build through your java code. Since you're trying to set a menu, the end result is that your custom field is a NamedID object. You'll set the lookup name of the menu to one of the three values that you give above.
I'm a C# guy myself, so my example is in C#, but it should be easy to port to Java using the link above as an example too.
public static void SetMenuTest()
{
Incident incident = new Incident();
incident.ID = new ID();
incident.ID.id = 1234;
incident.ID.idSpecified = true;
GenericField customField = new GenericField();
customField.name = "user_type";
customField.dataType = DataTypeEnum.NAMED_ID;
customField.dataTypeSpecified = true;
customField.DataValue = new DataValue();
customField.DataValue.Items = new object[1];
customField.DataValue.ItemsElementName = new ItemsChoiceType[18];
customField.DataValue.Items[0] = "Free";
customField.DataValue.ItemsElementName[0] = ItemsChoiceType.NamedIDValue;
GenericObject customFieldsc = new GenericObject();
customFieldsc.GenericFields = new GenericField[1];
customFieldsc.GenericFields[0] = customField;
customFieldsc.ObjectType = new RNObjectType();
customFieldsc.ObjectType.TypeName = "IncidentCustomFieldsc";
GenericField cField = new GenericField();
cField.name = "c";
cField.dataType = DataTypeEnum.OBJECT;
cField.dataTypeSpecified = true;
cField.DataValue = new DataValue();
cField.DataValue.Items = new object[1];
cField.DataValue.Items[0] = customFieldsc;
cField.DataValue.ItemsElementName = new ItemsChoiceType[1];
cField.DataValue.ItemsElementName[0] = ItemsChoiceType.ObjectValue;
incident.CustomFields = new GenericObject();
incident.CustomFields.GenericFields = new GenericField[1];
incident.CustomFields.GenericFields[0] = cField;
incident.CustomFields.ObjectType = new RNObjectType();
incident.CustomFields.ObjectType.TypeName = "IncidentCustomFields";
}