Forget about tessellation and compute shaders. You simply want to maintain a system copy of the terrain and send it (or parts of it) to the GPU every frame. Yes it's slow, but it ain't that slow :)
The trick is to make the section your updating small enough to not bog down the computer. So you don't want to be updating a terrain 1000x1000 tiles. Use chunks of terrain, I use 16x16 tile chunks with 4 tri's per tile, indexed. I can update a terrain chunk in real time no problems.
I was going to suggest a dynamic vertex buffer, but you don't even need that.. here's the code i use to update geometry, just use the default resource usage :
public void SendToBuffer()
DataStream data = new DataStream(vertices, true, true);
DataBox dataBox = new DataBox(0, 0, data);
device11.ImmediateContext.UpdateSubresource(dataBox, VertexBuffer, 0);
you just have to provide the vertex data, which you've edited during the frame. Maybe even read about dynamic buffers, they might give you even better performance, but I don't know about that yet.
edit : Just to clarify, this is SlimDX (DX11) code, so it should translate easily to straight DX11 code.
edit2 : And just to answer one of your questions above, you can also have flat geometry and use the vertex shader to shape your terrain, but you still need to get the height data in to your shader. So you can avoid sending new geometry in, but then you have to send a height map in. So you are still updating gfx resources. Which is faster depends upon your vertex and height map formats.. importantly, their data sizes. In my case, the terrain only has Position & Normal, so it's not too large. My UV's are derived from position. And I think by updating the vertex buffer itself, then it's done, and you've got your vertex heights precalculated, rather than having to sample from a heightmap, which does have a cost.