I was facing the same issue with my Java application. The API worked just fine in Postman, but had the "PATCH method not allowed" exception when called through the Springboot application. I used this code to access this. FYI, I also tried adding ?_HttpMethod=PATCH for the post method, but had no luck.

String url = UriComponentsBuilder.newInstance()
  .scheme(protocol)
  .host("your-salesforce-instance-url")
  .path(apiVersionPath + "/sobjects/Case/" + caseId)
  .toUriString();

PostMethod postMethod = new PostMethod(url) {
  @Override
  public String getName() {
    return "PATCH";
  }
};

postMethod.setRequestHeader(HttpHeaders.AUTHORIZATION, "Bearer xxxxxx");
ObjectMapper mapper = new ObjectMapper();
String body = mapper.writeValueAsString("your-json-request");
postMethod.setRequestEntity(new StringRequestEntity(body, ContentType.APPLICATION_JSON, "UTF-8"));
HttpClient httpClient = new HttpClient();
int statusCode = httpClient.executeMethod(postMethod);