This was mind bugling for me for some time now, every method I tried gave me some kind of error such as broken child category or broken pagination. But at the end I found out the simple solution without of adding any Plugin or editing .htaccess file… To make this work you will need to create the page (in wp dashboard) and page template for every category (this will add possibility of custom category template for each individual category as well).
Edit page template for example page-news.php and set it up to show category, I done something similar earlier in tutorial How to create Page with two columns, so follow this tut if you don’t know how to do it. In Dashboard / Page create new page and assign your new template to the page. One more important thing is that alias (slug) of your page is the same as the alias of the category.
Now when everything is set up, for example you have category “News” with slug “news”, you created page “News” with slug “news” and template “page-news.php” assigned to page “News”, go to Dashboard/Settings/Permalinks and under Custom Structure enter /%category%/%postname%/
Than under Optional Tab under Category Base enter . (just one dot) and save your settings.
That should be it, now every url with category base like this – www.example.com/category/news/ will be shown like this – www.example.com/news/
This way you will actually replace categories with pages and open numerous page specific options.
Using this method I achieved Child categories to work normal and pagination is not broken as well, no errors so far.