Regarding the first scenario:
It is a good practice to avoid orphaned items; my advice is to stick to 10 users per page and show 11 users at 4th page. Now if you delete all items on 4th page, remove the page number from pagination and take user back to third page.
Regarding the second scenario:
It will be best to update the list in real time via AJAX and remove deleted items right away (updating pagination right away); it will help you to avoid additional edge situations (for example the one where User1 will call delete on item which was already deleted by User2).
Now regarding the pagination itself:
It is a bad idea to introduce it as a way to navigate through long list of items. You can have 2 scenarios:
First one - the list is short (lets say less than 100 items) which means you can show it as is, maybe with a way to filter and sort it; introducing pagination in this situation will only complicate things for user and bring extra friction into your application.
Second - list is long (200+, 300+, 1000+) which means you are doing something wrong and probably user should not see (and in most cases does not need to see) the entire list. In this case pagination is not a silver bullet either. Also, by avoiding pagination you will avoid situations like the one you are solving; pagination only introduces needles friction for both you (by forcing you to think of stupid edge situations) and your users.
Here is more reading if you are interested in spending time thinking about pagination:
http://www.codinghorror.com/blog/2012/03/the-end-of-pagination.html
http://www.slate.com/articles/technology/technology/2012/10/website_pagination_stories_should_load_into_a_single_page_every_time_.html