Hey all, 

I figured out how to do this on my own and thought I would share for posterity.  I used an HTTP webservice to move the attachment in the first place using the URL------- (‍{Workflow Context:Current site URL}‍_api/web/lists/GetByTitle('‍{Workflow Context:List Name}‍')/Items(‍{Current Item:ID}‍)/AttachmentFiles) ------  I also used the "HTTP Get" request type in the web service action.  This worked great.

I then copied the web service action and placed it at the end of the WF.  I then added "getByFileName('‍{Variable:AttachmentFilename}‍')" (for a final URL of   ----‍{Workflow Context:Current site URL}‍_api/web/lists/GetByTitle('‍{Workflow Context:List Name}‍')/Items(‍{CurrentI tem:ID}‍)/AttachmentFiles/getByFileName('‍{Variable:AttachmentFilename}‍') -------

I then changed the Request type to "HTTP Delete". 

No other changes to request headers or content. 

It took me hours to figure out, but the more more I learn about REST lingo, the more it makes sense.

@cbeene , I am trying to use this same process, and I have the syntax right but it's returning status code 403. I'm the owner, so I have full control over the list so I can't figure out why it's forbidden to remove the attachment. Any ideas? It also errors on file names with spaces, but I can live with that. BTW, I'm using Workflow Cloud.

@AnneC  - 

I’m not sure that I can help much here as I don't work in Nintex Cloud OR know a lot about REST permissions. Sorry.  Having said that, let me ask something based on what you stated.  Are you able to copy the attachment with the first web call, but not delete with the second?

@cbeene , thanks...

I went back to O365 designer and got it to work, no problem. So I duplicated the URL string in NWC exactly and it gets the "403, Access denied. You do not have permission to perform this action or access this resource."

I'm using NWC because it builds a collection for attachments automatically and also has a "get attachments by name" function, neither of which exist in the O365 version. And, while I can clear the attachments collection, there's no function to update the Attachments column in the list so the attachments remain. Too bad I can't call the O365 workflow from the NWC workflow!
If I figure it out, I'll post it here for posterity like you did, it was very helpful.

@AnneC, you may have figure this out but it sounds like it is true an authentication issue.  If you haven't already, I would look for an article about REST or HTTP Request Authentication from NWC.